If this is as widespread as it seems, perhaps the manufacturers should fix the OS to do something about it. Banning "anything that links known SDK x, y or z" is just whack-a-mole.
One simple approach that comes to mind with minimal thought (aside from the obvious "why the fsck does a Pac-Man game need network access at all?") is having the app manifest contain a list of domains to which the app intends to connect, and block anything else at the OS level -- perhaps blocking everything by default, then permitting IPs when the app uses the system resolver to resolve a whitelisted name. Then scale the degree of (human and automated) scrutiny applied to the app with the size and breadth of the whitelist. You can still make a web browser app or something that gets unrestricted access, but it gets a lot of eyes on it. Maybe have to provide source for review. For most apps, "you get five connect() calls per minute unless your manifest declares a good reason for more" might be helpful as well.
Perfect? No, but it increases the complexity and expense of automated spamming/DoS/scraping attacks without proportionally increasing the cost of legitimate behavior (even undesirable legitimate behavior like ads), and funnels potential malfeasance through smaller and more observable chokepoints. Get caught serving a million subdomains to route spam traffic via your one whitelisted domain? Congrats, your dev certificate is now revoked and none of your apps work anymore, and anyone who paid for them gets automatic refunds.