Do you tend to host just the one game at a time, or do you run mutiple game servers? Do you have additional stuff like teamspeak, forums? Does your host provide you with a standard setup you can tweak yourselves a little, or do you totally control your own box performing all your own installs and setups?
Realsitically are you a dedicated or shared server user?
Location is critical, as is the tier in the server rack. It's no good ending up somewhere with appalings pings for the majority of players. If your clan is mainly UK based, then a UK server, otherwise Europe would be good, but avoid USA it's just going to be too slow.
I know
www.i-websolutions.co.uk are branching out into game servers. Indeed the nthwclan has a dedicated server running through iwebs rackspace.