OK, well, it still sounds like a codec issue, but are you overclocking or undervolting? I've had problems with accessing files from a microSD when undervolting substantially, the "ideal" profile works OK.

If you want to try and diagnose the problem without a reflash I'd be tempted to suggest logging into the phone via SSH, installing mplayer and running it from command line against any videos you're having a problem with.

It should hopefully either start playing the video, or output some useful diagnostic information such as what codec it is missing, which may guide you as to what else to reinstall. (edit: some fishing around on my N900 suggests I also rely on libavcodec52 and libxvidcore4)