Well.. The resolution which the phone uses is at 400x240. So, any video which can be cropped in these dimensions will play in Full Screen. If you're downloading videos from YouTube, make sure you download them as 360p (640x360) they'll play perfectly in your phone :)

Actually Nokia does good by not stretching the videos to full width. This will only worsen the quality of content displayed and nothing better.