Has anyone looked at other hosts? The hosting business is cutthroat, and there are a lot of them out there that are good and want your business. If the deal to have either a dedicated server, or at least a minimum bandwidth were agreed upon up front, you might find it wouldn't cost much more than it does today. Just my 2c.
