Before my AppleCare ended on my 17in PB G4, I called and asked if they would just send me some feet (2 had fallen off at that point, now it's 3). The answer I received was no. This call was probably in late 2006. Good luck!
(And btw, the foot pads on the base of the new unibodies are a significant improvement - just one of the many reasons I am loving the updated design.)
Did they offer to send you new ones a a small fee.?