Sitemap конечно важен, но из-за него вы не могли выскочить из выдачи.
Вариантов несколько:
1. Вы сделали то, что негативно повлияло на ранжирование (например, опубликовали неуникальный текст, выгрузили некачественный код, попали под фильтр за переспам, нагнали некачественных ссылок, изменили внутреннюю перелинковку и т.д.). Здесь нужно разбираться детально.
2. Вас подбросило сначала на 5-ю, а потом и на 4-ю страницу по технологии Многорукий бандит. Это специальный алгоритм Яндекса, который периодически "подбрасывает" новые сайты на высокие позиции. Если пользователи на это хорошо отреагировали, вы можете на таких позициях остаться. Если ничего не изменилось, то вас опустят обратно.
Сайт появился в поиске, но только по низкочастотным запросам.