How peculiar. How did they discover these things? How do they do that, overall? I lack the knowledge required for that and can't imagine the process.
Tessellation is pretty cool, and to me this is just a form of that. I imagine it's a lot easier now with computers, you could probably throw together a genetic algorithm that mutates a shape until it finds one that gets 100% coverage; I'm sure there's probably some favoured angles or such as well.
You just need to provide a gradient for the search space. Something like inverse of average gap between tiles. This is standard for any metaheuristic search (of which genetic algorithms are a sub-category), so I wouldn't call it "doing something clever".
Metaheuristics search a problem space to find an exact solution (total plane tiling). In order to search that space, they need direction. The "almost plane tiling" is the direction. You said it would be difficult for a genetic algorithm to find a solution because the set of solutions is very small, but that's missing the point of a metaheuristic. It's the difference between climbing a hill and a cliff. Either way the goal is at the top, but the hill is easier to get up.