http://www.eurosimm.com
They can sell you a new laptop without OS. That's where I got mine from, so I can attest to its Linux-compatibility (Mandrake 9.1 is my weapon). The only thing that doesn't work is 3d acceleration, as my notebook uses an sis650 video controller and there is no DRI support in the xfree driver for that hardware, but I think some of their newer notebooks may use ATI technology so you may be luckier there. Check them out anyway, they're quite cheap too.