FWIW, I just installed Parallels Tools in the upcoming 10.04 release. After making sure that there's a proper compiling environment (I used the "sudo m-a prepare" command, the module-assistant package is needed for that), Parallels Tools installs fine with the "sudo ./install" command in the /media/Parallels\ Tools directory); the installer asks to install some missing stuff, which I allowed.
So, for all of you suffering folks with 9.10, your suffering will soon be over when you upgrade to 10.04 next month (or right-away if you're the adventurous type). There's a nifty little feature where the upper left corner of the screen folds back like a page to show the underlying Mac OS X screen...