Hi
I want to share my experience with a hoster I discovered about a year ago: https://serverastra.com/
I set up a non-exit relay in feburary 2012. They offer a VPS with 100Mbit unmetered traffic for about 15$/month. Here are the vnstat stats: http://paste.scratchbook.ch/view/26af6ae0
Recently, I asked them if I am allowed to run an exit-relay. They answered:
-- For now our ToS allows Tor nodes. but please be advised they are really easy to abuse. We will try to protect the network with our firewall in case of problems (we already experienced spam from ToR networks). In any case a ticket will be opened upon abuse case and we will try to keep both sides confidentiality during negotiation. Happy New Year! --
They are really cooperative! They also set me up a reverse DNS. So everything runs fine and fast. Although they sometimes encounter problems with DDOS-attacks, which affects the bandwith. But this only happened twice last year.
Claude