I've replaced the PRAM battery, it didn't work for me.
Zack, after the some more research, I believe the problem you're describing ( I have exactly the same symptoms, including the beeping when removing the memory chips) is related to the NVIDIA 8600GT graphics processor overheating and popping 1 or more of it's solder connections.
Jordan, the problem you're describing is almost certainly the famous NVIDIA 8600GT issue.