http://www.imtoo.com/3gp-video-converter.htmlFound this - not MP4, but 3gp which is still compatible for mobile phones.
I have used it to convert videos from my pc, and bluetoothed them to my phone. No watermark etc - max convert time limited to 5mins (make sure you click cancel when it asks for your licence number - it then only lets you have the trial version, which limits the 5min).