mick:
Forgot to add - take a look at http://www.edis.at/en/home for example. They have reasonable offerings (but limited on the KVM option) in a variety of countries and I have already established that they would be comfortable with non-exit tor relays.
Be aware that depending on the data center, the KVM nodes at Edis get rebooted fairly often ... if you want to run a larger relay and be flagged stable, maybe not the best choice.
-Gordon