I first came across this when I was looking at the Surly LHT, but I started to see it everywhere. It seems to me they can just put on a longer fork or something, or is it more for the back wheel?
The real issue is in the top tube length. Basically, for shorter riders you need to move the handlebars closer to the seat. But then you have to deal with the wheel possibly colliding with the pedals ("toe strike"), changing the head angle or the fork's rake, which compromises the handling, and/or having a proportionally longer top tube than would otherwise be indicated by the seat tube length.
Rodriguez Cycles did an excellent multipart essay on choosing between 650c and 700c wheels for road bikes, and the illustrated Cliff notes they provide should prove illuminating.
A bike frame does not have to be above 56cm at all. In fact, the 56cm is a measure of only one aspect of the bike's geometry.
It depends greatly on the bike. The Long Haul Trucker, for example, my only be sold in frames 56cm and above, but several other Surly bikes, such as the Cross-Check and the Pacer come in sizes as small as 42cm.