I have an older Compaq Armada (it's a P3 600MHz, so it's finally starting to wear out), and I've been fairly pleased with it. As much as I hate their desktops, I'd probably buy another of their notebooks if the need arose.
That having been said, I'm not big on notebooks as desktop replacements. You always run into random hardware deficiencies or design flaws, and it's much harder to get the hardware you want. Plus, if the screen or other devices crap out, it's a pain in the ass to make sure that your HDD data is retained when the unit is sent in for service. Unless you really need the portability, I think you'd do well to just build your own micro PC for about $500-$600. Micro ATX cases and mobos are relatively prevalent these days.
