Предоставляют ли местные провайдеры или фирмы выделенные сервера без привязки к определенной ОС? что-то типа http://www.elters.ee/ru-RU/Dedicated/Default.aspx

Dedicated? Да, конечно. Это обычное дело.
Самый удобный вариант хостинга, как для провайдера, так и для клиента.
Под это дело помещение есть, стойки и т.п.
У нас в фирме Doran этим занимается. Как появится на форуме, то, думаю, распишет подробнее.

Ок. По какому телефону можно связаться и обсудить детали? Какая стоимость, какое оборудование? Какой канал? Ограничение трафика? Ограничение ОС? Способы оплаты из-за рубежа (WM, PayP etc.).

Нужен именно в Эстонии?

По большому счету нет, если установят необходимую мне ОС с минимальными конфигурациями и затравят SSH.

Нужен примерный конфиг и/или сумму, которую планируется потратить.
Есть хорошие предложения в Германии. Любая ОС.