I have run into that bug myself; it only went away when I emailed support and let them know. Got no other answer than that, other to make a new adgroup for your new ads. You lose your history, but there it is.
Well they can't really *delete* anything permanently, because that borks the reports, in case you wanna go back and get reports from 2004 or something. But they should put in some fix to get around this issue.
Phone support - sometimes it works. I haven't had trouble with it, but others have told me they can't even get through. So maybe it depends on which user id you type into the keypad.
The consensus in the database world is that you never delete anything. Netmeg's comment is the main reason why. Most database systems have a delete function but all that does is mark a record so that it doesn't show and is not used in reports if you don't want them to be (I believe Adwords includes any deleted records in reports).
I don't think there's any way around your problem other than create a new group.
the checker runs back to check too frequently, so sometimes when you're switching things over, it visits during the time when both are there and flags things.
if there's just a few ads, delete them all, wait an hour, enter the new ads.
and G, make the nazi checker a lil slower in looping back around with his marker. there are legit times when a changeover is happening - perhaps you can make the soup nazi continue to loop after the flag is set, and give him an eraser.
Say you have 25 keywords in an adgroup, and the ad points to one url, but for a couple of the keywords, you want to use a different landing page. You can set JUST THOSE KEYWORDS to go to that different landing page. So then, if you change the destination url on the ad, it's possible to forget you have a few keywords pointing to a different destination url, and they're still left hanging. I've forgotten those enough times that I remember to check now.