I think, the easiest way would be to just email google at
mailto:adsense@google.com or take a support ticket on the Google Adsense Support site. I have seen Webmaster Services that use this technology and work, but I do't know if Google allows something like this. Other way if google wouldn't allow sth. like this, the big Webmaster Services would stop...
So maybe only wit an special "You are allowed" email from google?
Interesting would be if you host full sites like guest books for your users or only sth. like "include this code" if you are worrying about not being your one content for Google Ads.
To "Ad Publishing service that you think would do the job in our scenario?" : I think there is an Service from ebay called "relevance ads" and there also is one from overture!
Just search a bit in the Web ( fortunately woth Google
)
Hope, I helped,
greetings,
lionstarr