An illustration of @Toscho's nice idea, from Steven Dutch's Rep-Tiles webpage:
![reptiles][1]
"Four squares can be arranged around a central square to form a Greek Cross. Greek Crosses make a lovely plane tesselation, but they are not rep-tiles. We can try modifying a Greek Cross tesselation by replacing each cross with the compound of five crosses. It's closer, but still not an exact rep-tile. We can repeat the process, each time getting figures that are more and more crinkled and closer to a true rep-tiling. But at every step, we see that the perimeter of the tiling always has twice as many crinkles as each tile."