I actually bought a stripped Pac-man that was painted over at the W-S auction a few months back. It was $65. It didn't have the game, monitor, or marquee but what was left of it was in fairly good shape (cabnet itself, controls, PS, coin door, bezel). I was told this was a good deal. I've seen completely restored Pacs and Ms. Pacs go for $800. These are sold in the morning on the "classic row" and the prices seem unreasonable to me. I would hold off until later in the day when the crowd thins out and auctioneers start selling the beat up, parted out, and converted cabnets. I would expect a mostly complete but not working pac-man to go for around $200-$250. You could do what I did and just look for the classic pac-man shape which has been converted/gutted. I guess those go for $65-$150. Also remember that Ms. Pac-man always goes for more than Pac-man. I would highly recommend you go to the auction if you want a pac cabinet. I can almost guarantee there will be at least 10 of these machines at Winston-Salem because, like Paige said, they are still very common. They do charge a 10% fee for people not "in the business" and I think they charge you if you use a charge card.
Hope this helps,
Matthew