I have been running FS2k for the past 6 weeks or so. It works very well with frame rates of 15-45. I fear your problem is your graphics card. Certainly 500mhz is fine but the GC must have the ability to cope with it.
I run a Celeron 400mhz, 128mb Ram and Matrox G400 card. This combination is very good and performs as well as any, and better than most. TNT has turned out to be difficult and Voodoo has problems too.
On a laptop? Not so sure about that. Don't think Microsoft considered that. It does work on a PC and the swoftware is good, with just a few bugs which are countered in a patch that is due out tomorrow from their download site.
You can e-mail me if I can be of any further help.