What if you dynamically updated the same mp3 file instead of updating the media file URL (and changing the guid.)
As far as cached mp3s that are already downloaded, I don't see why that should have a huge impact on ads. The most important episode for advertising purposes is probably the most recent episode, and if someone pulls an archived mp3 that should have the new ads too. As for already-downloaded, cached mp3s you just gotta let those go.
This is the reason why you just cannot create dynamic ads if you want to stick to the standard RSS+client approach (like iTunes).
Some of the podcasters have started actually building their own native apps to have better control of the content they emit, but it comes with reduced visibility. This is why most of podcasters still release their stuff through iTunes, but invite the listeners to download their app.