Not all H.264 encoders are the same. From your message it would appear that you’ve tried both the Quicktime and Squeeze encoders.
What you can’t rely on with either of those tools is the quality and suitability of the presets that come with them.
It may take some time to find the right balance of quality, file size and time taken. Higher quality output (nearly) always takes longer and results in a larger file.
You are on the right lines, exporting as a QT ref movie and then taking that into Squeeze or whatever..