Early firmware versions only played nice with Mpeg4, however most videos you get from the innerwebs are divx or xvid and so far with my 2.10 I have only had a few I needed to re-code.
As far as I know, .mpeg and .mpg are also played fine even at firmware 1.5 (this is the lowest firmware for me, because I have got a European 60GB PS3)