Ok an update.
"My Videos" folder now contains:
2 xvid files downloaded from internet
1 mp4 file from my k850i
1 mp4 avp requiem trailer from PSN
1 mp4 gt5 trailer from PSN
Now as soon as I moved the xvids into that folder they showed in WMP11 (whereas the file from k850i already in that folder would not show in WMP11 video library). I also added the 2 PSN filees to the folder and they do not show in WMP11. My understanding is that unless they show in WMP11 first they won't show on the ps3.
A quick google shows that their is some sort of problem with WMP11. It will play back mp4 files natively (if you open them) but it won't show them in it's library, so would not show on the ps3 as a result.
http://boardsus.playstation.com/playstation/board/message?board.id=ps3media&thread.id=47970
http://a8t8.spaces.live.com/blog/cns!2518DD508BB713E8!156.entry
I have not read it fully, but looks like some patching of windows etc has been done by those 2 articles (to make the mp4 container viewable in WMP11 library).
HOWEVER, the 2 pages imply it is a problem to the 360 as well as ps3. As you only have this issue on ps3, it may not be the same issue as you have (although displaying similar symptoms).
Quick way to check (I think) is go to video library in WMP11 and see if you can see the files in there, that don't show on ps3.
rp2000
Edit: info came from googling "ps3 wmp11 videos mp4" but I have not read the full details of either fix. If you don't know much about computers/windows etc do not be making any of the changes listed in those articles, and deffo don't be coming my way if you do
