I have the exact same symptoms on my system. The highest I can go without the screen being garbled after the splash screen is 1280x1024. I haven't tried the virtual screen stuff - sounds like an acceptable interim solution - but I'd like to get it to work without dirty tricks...
I run this:
PIII 800 MHz
GeForce2 GTS 32 Mb
ASUS CUSL2-C mobo
384 Mb SDRAM
LFS, kernel 2.4.20 xfree86 4.3.0
nvidia module 4363
The 'nv' driver from xfree works fine at 1600x1200.
I also have a gentoo system on the same box with the latest nvidia drivers (should be 4363) and it works at 1600x1200. I've tried using the XF86Config from that setup, but it doesn't work.
Not very helpful, I'm afraid, but at least you know you're not alone.