My standard toolchain is ( x264 -> rawvideo + faac or NeroAACEnc -> aac audio ) -> mp4box -> mp4 file. For those who are commandline-phobic, there are many GUIs to streamline the process; for example, MeGUI can produce Flash-compatible H.264 video files with x264.
Make sure you're using the latest versions of the encoders as well, especially if you're trying to get away with a much more fancy video than the one in the parent--it's better quality and compression for free.
Also remember that Flash supports H.264 all the way up to High Profile, so there's no reason not to use all the features.
(aside: above video uses a ~2007 version of the encoder, according to my detection tool)
NB: This comment was made after this thread went dormant. This cross-post is for the benefit of anyone browsing the archives..