"AFAIK Google adsense for search comes with its own everything (searchbox + searchresults + ads) and there is no API to simply fetch ads on the query terms."
This is where you are wrong. Google does give out XML ad feeds.
This is where you are wrong. Google does give out XML ad feeds.
Also, I believe (but am not 100% sure, and certainly don't want to be quoted on) that: 1 - AFS pays very competitive rates; 2 - in order to get an XML feed, you will probably have to agree to exclusivity. This isn't all bad though as you often get a better rev share if you go exclusive. Typical periods are two years.