There are also limits on disguising search results as ads.
>For the rest, there's not much short of an acknowledgement overlay that will get the message across reliably (for text ads -- image ads are easier, but google doesn't have them)
Really? Just increasing the contrast or adding a border around the border or using extra spacing as a separator or another separator can help a lot. But it's hard to make changes that hurt the bottom line. Changing it the opposite way is much easier. Google has a lot of UI and UX experts and I don't think the changes are accidental at all. In fact, they must be very carefully planned.
Edit: Found an old screenshot where the difference is much more apparent.