Провайдер заблокировал сервер. Нужен совет по проверке (Ubuntu 12.04)

Здравствуйте,
Возникла такая неприятная проблема. Есть выделенный сервер, арендованный у рег ру, система на нем стоит ubuntu 12.04 32 бита. На сервере бэкэнд для пары игр в контакте и одноклассниках (сокет сервер на джаве+дерби база данных, апачи2+ mysql+php).
Собственно все. Больше он мне ни для каких целей не нужен.
Позавчера мне поступило уведомления от провайдера, что мой сервер кого-то там атакует. Прислали логи атак, и саму жалобу от superb.net. Не знаю были ли атаки на самом деле, или они так у конкурентов клиентуру отбивают, но суть не в этом. Айпишник сервера заблокировали и попросили устранить причину блокировки. И тут я был просто в ступоре. Знать бы еще что устранять. В общем,
сейчас у меня есть к нему доступ только через kvm. То есть на сервак я зайти могу, но установить что-то из репозиториев или вообще откуда бы то ни было из сети не могу.

Действия которые я предпринял:
1) Просмотрел всевозможные логи, от логов ssh (в которых, кстати были неоднократные попытки сбрутить систему, но везде окончились фейлом, так как пароль там довольно сложный),
2) проверил логи установок, в которых тоже ничего подозрительного не нашел.
3) Дальше решил забить на возню с этой учеткой, удалил ее и создал новую УЗ, с абсолютно новым паролем, еще более сложным. Никаких данных из той в нее не копировал (может это и бред, но чтоб уж наверняка ничего с копией не пришло)

Так как на сервере линукс, то антивируса я туда в принципе никогда не ставил. Просто всегда подходил ко всем установкам ПО с головой. Но, видимо, где-то что-то все-таки недоглядел, либо жалоба фальшивая.

Сейчас провайдер спрашивает какие меры я предпринял. Ну, я им отписался о том же, что написал выше.

Вот сейчас возник вопрос, а что можно еще предпринять, не имея доступа к сети?
Понятно, что универсального способа не существует. Поэтому я и прошу подсказать, куда еще можно попробовать копнуть и что проверить

п.с. Переустановку системы советовать не нужно. Этот вариант я оставил напоследок, если ничего другого сделать не удастся