my oldest notebook in use is a thinkpad x21 with a mobile p3 (500-700mhz) and ram maxed out at 384mb.
after using lmde for a while (deactivating mintmenu gave back quite some responsiveness) i've tried replacing gnome with xfce, and later lxde, and finally got back to gnome, but with openbox as wm instead of metacity. the system ist very responsive, and i have all the goodies i need (and have become used to) in gnome, like easy proxy management, which i need for beeing online via my cell phone.
next thing i will try is replacing nautilus with another file manager, and some other little things like gpicview...
"I'm not a complete idiot! Some parts are missing!"
mobile dwarf: E³901 ShinyWhite, 2GB, 32+4GB, Ubuntu 10.04 LTS, BIOS 2103
great-grand dwarf: IBM ThinkPad X21, 384MB, 80GB, Linux Mint Debian Edition (rolling)