Hi Rich,
I cleaned up a clients site using a method similar to what Derk described. The developer basically kept all the site exactly the same, removed infected areas and then let Google know. The vulnerability was in an old plugin.
It took 24 hours and the 'this website may be hacked' was removed by Google. I dont think it is as dire as you think as long you have a competent developer.