А что менялось за последнее время? Попроси еще у хостера конфигурацию виртуального сайта.
Неплохо было бы посмотреть логи во время запросов на неработающие хосты.
В rewrite может быть причина - у меня нет аргументов, но возможно механизм такой:
ServerName shevchenko.sheva.name
ServerAlias *.sheva.name
ServerAlias sheva.name
ServerAlias www.shevchenko.com.ua
Ты набираешь http://sheva.name, сервер должен добавить завершающий /, и на автомате преобразует хост в ServerName, т.е. http://shevchenko.sheva.name
А если наберешь сразу http://sheva.name/, то все должно работать. А если не работает, то действительно может rewrite не срабатывать
Я сталкивался с похожим. Wildcard host не работают так, как хочется в условиях виртуального хоста...
Слегка сумбурно... Но может поможет...