We're able to swap out Google's sponsored results in many cases but not all. There could be a couple of causes of this:

1) Google's HTML structure is very unique, apparently to save bandwidth so the page loads faster. There's no closing </body> tag, for example.
2) The HTML Google returns is not always the same. Different queries can return significantly different HTML (different beyond just the details of what you searched for). It's possible Google is intentionally creating a moving target.
3) Google dynamically loads extra external JavaScript from it's own servers on every page (in addition to the copious amounts on inline JavaScript). It's possible that external code dynamically removes any script tags we've added or otherwise modifies the page in some way.

The odd thing is how this issue appears, however. Basically, the DOM sometimes contains the classes we're looking for, and it sometimes does not. Looking at the generated HTML, however, the classes we're looking for always *appear* to be there, but they're either somehow inaccessible or appear to be there in things like FireBug when in fact they're not.

It's possible we need to build our own dynamic DOM walker that shows what's actually there at the time our script runs.

Finally, it's possibly they're somehow loading the DOM into a different page "document." I'm not sure how you might accomplish that (sneaky iframes?), but a thorough attempt at walking the DOM should at least reveal something.