Tricked Out

I've been trying and trying to get movies to playback on my pearl. I have all the encoding software. I've tried mpeg4, .avi, wmv, mpeg2/1, 3gp.....the movie starts playing and then it seems like the player bogs down and it freezes up. Error messages occur and a message stating that the file is in an unsupported format. Anybody have any luck with this? I've heard people doing it on an 8100 and no probs, even an 8830 and no probs. It's very frustrating. I've compressed the files down to 250-400mbs, it shouldn't be the size of the file.
I've saved it to a memory card. There's plenty of space and memory.

Any tips would be great....