No one has mentioned this yet, but it depends on the iPhone / iOS device.  In making an app that tries to copy Flickr videos to the photo album, I was getting frustrated when I kept getting invalid data results on writeVideoAtPathToSavedPhotosAlbum: calls for a non-Retina iPhone. 
I ran some videoAtPathIsCompatibleWithSavedPhotosAlbum tests on Flickr videos of various sizes, as requested in this question.  
                                  iPhone        iPhone       iPad
                               (non-Retina)    (Retina)
6119419764_orig.mov
H.264, 1,920 x 1,080               NO             NO          NO
Linear PCM, 16 bit 
little-endian signed 
integer, 48000 Hz, 
Stereo (L R)
35.33 Mbit/s
6119419764_hd.mp4
AVC Coding, 1,280 x 720            NO             YES         YES
AAC, 44100 Hz, Stereo (L R)
2.15 Mbit/s
6119419764_site.mp4
AVC Coding, 640 x 360              NO             YES         YES
AAC, 44100 Hz, Stereo (L R)
833.71 kbit/s
6119419764_mobile.mp4
AVC Coding, 568 x 320              YES            YES         YES
AAC, 32000 Hz, Mono
775.14 kbit/s
6121206003_orig.mov
(Taken with iPhone 3Gs)           
H.264, 480 x 360                   YES            YES         YES
AAC, 44100 Hz, Mono
865.94 kbit/s
30 fps
6110638568_reformat.mov
H.264, 640 x 360                   YES            YES         YES
AAC, 44100 Hz, Mono
3.57 Mbit/s
Based on this limited testing, for a given format and device, it looks like size matters most. (For the current Flickr encoding methods and url scheme, mobile videos work on all iOS device photo albums, whereas hd and site videos only work on Retina iPhones and iPads.)
An interesting side note is that HD videos will play on non-retina iPhones with the MPMoviePlayerController -- you just can't save them to the photo album.