What is the correct format/resolutoin for videos on an HTC Wildfire?
Have you tried using VPlayer?  It should handle any mp4, avi, divx, etc. video that you throw at it, without the need of converting it.