Apologies for not posting this in AdWords but I thought it might have more relevance here.
I use Google UK and today noticed something rather wierd. I tried a search for a 'service A London', then tried another one for 'service B London'. Some of the PPC ads were for service A! Then I searched again for 'service A London' and some of the ads were for service B!
I got a friend at a different location to check this. They found the same thing until they switched back to 'service A London' - that time everything was correct.
I still see this right now as of posting. It doesn't matter what service I use, ads from the last service are being displayed.
I'm not logged in. I'm using the UK results only filter.
My first impulse is to say that organic search and Adwords relevance cannot be connected - after all, advertisers must bid on specific keywords. The ads on SERPs are not chosen by a relevance algo, although they might be filtered OUT from display automatically.
But this is a very strange report. Have you tried the experiment with cookies turned off?
Didn't G start this quite a while back. If you search for service A, then search for service B, AdWords sometimes assumes you might still be interested in A and show ads for them. Somewhat strange thinking on G's part, but I do remember reading something along those lines.
We have seen the same for some time (UK) - even if you don't search for service A first - I have never minded our ads showing for related searches. The natural SERPS however are always different - although of course the same sites may appear somewhere if they deal with service A and service B.