Потеря позиций из-за хостинга

John Gold, Меняйте свой хостинг, и не экономьте на нем потому что возьмешь дороже хостинг и качество услуг будет лучше, ну после пару апов ваши страницы вернуться в поиск как и было все.

Потихоньку все возвращается...

Поставил uptimerobot, чтобы проследить за хостингом... Обрывы довольно частые, особенно по ночам.

Скажите, а стоит ли перейти на VPS? Послужит ли это плюсом для ПС, в плане уменьшения время отклика. Или при небольшой посещаемости разницы с обычным виртуальным (хорошим) не будет?

Стоит.

Был маленький сайт с небольшой посещаемостью, загружался медленно, хотя тормозить там просто нечему. После перевода сайта на VPS он начал летать и свистеть :)

Если ваш сайт и на VPS будет работать не быстро, то вы, по кране мере, сможете на это как-то повлиять (оптимизировать сайт, купить VPS получше).