That isn't actually true. Cleats or no, the power comes from the down stroke not the up stroke: see http://roadcyclinguk.com/riding/bike-fitting-the-myth-of-the... . While there are good reasons to use cleats (mostly so your feet won't come off the pedals), I haven't seen any evidence of significant efficiency gains. Furthermore there are plenty of ordinary shoes with sufficiently stiff soles to cycle in.
that's interesting.. i would have said from feel that accelerating and especially sprinting up hills i was pulling up - but perhaps the benefit is just that my feet are stuck to the pedal at the top rather than lifting off.