Inbound site wide links are not necessarily the kiss of death for SEO. I have observed that the effectiveness of inbound links at boosting pagerank goes down with each subsequent link from another site. After ten or so links from another site, Google pretty much starts ignoring the rest. Its the quality of the links that matter. The quantity doesn't help, but it usually doesn't hurt.
The times that I have seen Google penalize site wide links are for other reasons. For example authors of Wordpress themes that include paid site wide links embedded in the footer of every Wordpress theme that gets used. I have a site that gets lots of site wide links without any problems. It's a currency conversion site and webmasters use it on every page for converting prices.
In your case, you have some type of monetary relationship with the sites that link to you. That could put the links onto Google's naughty list. If the anchor text is keyword rich, that is another reason to worry.
- Ask your clients to nofollow the links
- noindex,nofollow the pages on your sub-domains so that you can't derive any benefit from the links (or put the sub-domains in robots.txt)
- Do nothing and only react if you get an unnatural links message or penalty from Google
- Disavow the links using the Google disavow tool (although Google says not to use it until you get a penalty, and that you should ask for the links to be nofollow or removed before you disavow).