After some experimenting it turned out that H.264 video needs to be encoded using the Baseline Profile for the HTC Hero (running Android 1.5) to be able to play it.
High Profile will not play at all on the phone. Main Profile will play, but gives an entirely green video – unusable.