On the Mac side, you may want to downgrade to 10.4, as it should run better on the hardware you have, possibly enough to turn Spotlight back on.

Online backup services, can't really comment there. Mine is a combination of MobileMe iDisk, and rsyncs to a Time Capsule at a relatives place back in Colorado. Not fully automated yet, been meaning to script something on my old PowerPC mini to open various time machine backups and send the files over on a regular basis.