Check out eGay and look at the IBM T series laptops (T20,T21,T22)
I got myself a T20 and WOW. Better than any dell, hp, compaq, gateway i've ever used. Once you go IBM, you will never go back.
The T20 has some "heat issues" where the bottom gets hot, but it doesn't bother me all that. I think the T21 and on fixed that problem.
Myself I recently just got my T20 (PIII650, 128Ram, 8G HD, CD-ROM, 8MB generic 3D video) for about 450 shipped. I think that was one of the best recent deals for a T20.
If you keep looking you can probably get a really good system for 800 bucks.