I have this same issue with my site, but in case anyone is looking for a solution---I have a tentative one: NetDNA (or MaxCDN if you're not looking at their enterprise options) has a XML-RPC API that lets you purge individual files. So you can delete something on your server, then push the purge to them.

So while things have been bad in the past--they're getting better. Having everyone try to use s3 as a CDN has really forced the industry to evolve.