This is the official list of media types officially supported by each BlackBerry. It doesn't appear to be the whole story — I've yet to make an H.264 file my 9300 will acknowledge. But XVID and MP3 in AVI seems to work for me.
ffmpeg converts pretty much anything to pretty much anything, if you ask it just right. I have tried any number of ffmpeg settings the phone doesn't like, and this one will play:
ffmpeg -i inputfile.whateverformat -vcodec libxvid -acodec libmp3lame -ab 256k -s 320x180 output.avi
For 16:9, use -s 320x180; for 4:3, use -s 320x240.
(If your video has mp3 sound already, you can use -acodec copy and leave out -ab 256k.)
Result: a video that actually plays. Even if the sound can take up more space than the actual video!
This applies even if you're on Windows and hate the command line. There is a vast array of really, really shitty graphical tools that claim to do the same job and are basically ffmpeg with a visual interface. They are the quintessence of crapware and don't actually make the job easier. Just use ffmpeg for Windows.
(The main problem with ffmpeg is that (a) it has options for EVERY obscure little thing (b) the documentation insists on listing every single one of them every time, which means that finding the options for the simple task you wanted to do is harder than it should be. Hence people like me being helpful with examples in blog posts.)
Hiccups: Sometimes libxvid will be a cock and give you "Invalid pixel aspect ratio 0/1". Replace -vcodec libxvid with -vcodec mpeg4 -vtag xvid and it should work.