High Volume Hosting Solutions

I maintain a news-oriented site which gets several tens of millions of page views per month. We've recently implemented an effort to include images in all of our articles. This is putting us over our bandwidth limit, which gets expensive very quickly. We are also having a minor dispute with the hosting company regarding the terms of these limits and the cost of purchasing more bandwidth in bulk.

I am recommending a CDN for hosting the images, or, failing that, another dedicated server to manage images and store backups and system monitoring data.

I would like to know if you have any particularly positive experiences with hosting companies for dedicated servers capable of supporting this level of traffic reliably, and what your experience with CDN services has been as pertains to calculating cost, performance gains, how outages impact the site, and integration with Drupal 6.

There may already be a thread or article about this subject, but I did not find it through searching, and so would appreciate any useful and up to date links.

Thanks for you help.