The other thing you'll want to try is in the video plugin configurator in ePSXe, set it to "compatibility mode", to lower the settings down. This will ensure that the emulator isn't trying to display something beyond its capabilities.
The one I'm trying at the moment doesn't seem to have such a setting, but I'll keep that in mind for whatever else I try.

Right now, I'm using E}|{'s Soft Driver K6/P1MMX 0.98. It works pretty well for a while, but it eventually starts to lag like a bitch. That's the problem I've had with any of them that worked. On top of speed and aspect ratio problems, they always started to lag like crazy after a few minutes. This one lagged every now and then, but always recovered until one point where it just started lagging every half second.

*frustration*

EDIT: Oh, and I'm using Street Fighter Alpha 3 to test them all. 2-D game. I don't know what's going to happen if I try Final Fantasy VIII.