I just replaced the memory on my G4. I used DMS (datamem). They were very sightly more expensive than some of the more standard online places ($119 for a 1GB stick vs $105-110 elsewhere), but they have a nice website that sorts out macs by specific model, allowing them to guarantee the memory will work. Granted, my memory's only been in for a day, but it fit, was recognized right away, and seems to be working just fine. I shipped via USPS for free (but no tracking) - I ordered on Wednesday or Thursday and got it on Monday.
I think it was on this board that I got the rec to use DMS.