Redmystic itself wouldn't of caused this. I suspect it's search engines crawling your site after the sitemaps were sent to them. The search bots typically spider with many instances so it'll look like 50 or so users are hitting your site simultaneously. Couple that with the large number of products you have on a shared hosting and yeah I can see how this might upset your provider.
I know you've disabled redmystic but here are few thoughts that could help:
1. Disable the sitemap generation part of the component. It will no longer notify the search engines. You should also delete the sitemaps located in /components/com_redmystic/sitemaps
2. There are some spidering adjustments that can be made in Google's webmaster tools. That may help
3. As your provider mentioned, upgrading to a virtual dedicated will help tremendously. This link can help http://redmystic.com/index.php?option=com_content&view=article&id=69:redmystic-validated-hosting-&catid=10:faq-answers&Itemid=18