I have a Nokia N97 and I can't watch MP4 videos downloaded from Youtube. I have to download 3GP versions which have pretty bad quality but it seems to be the only format that plays.
it does play mp4 videos, check ur specs
http://www.nokia.com/au-en/products/phone/n97/specifications/
the problem may not be the format, but the video resolution; if its higher than what ur phone can handle, it needs to be downgraded with pc software first if u want the hassle.