I have been dealing with this for a while now. My solution right now is to actually use two different themes, and the mobile theme serves a mobile ad based on detected viewport size. That's a hack, and the next thing we're going to try is just swapping the ad out in a single theme (again based on viewport)
Until Google comes out with adaptive ads (and they claim they are looking into it) that's about all we can do. I am going to keep beating them about the neck and shoulders about it, because in every other respect they are pushing for people to go into responsive design, and then they have this huge freaking gap.