I rented a relatively cheap server from OVH. It appears to have good (or at least not bad) routing for many countries in europe, at least I've tried that a couple of people from different countries play on that server. Of course I wouldn't know how you could order the server yourself, as the SP (service/server provider) I'm talking about (or the SPs I know in general) are only German ones, and so are the sites where the info and order-page of the products (servers) is - they are just in German.
The most interesting thing will be the routing to the provider you are looking for anyway. Once you know a provider with good routing, it's only your purse that decides about the nexuiz-server performance. Usually people rent dedicated machines running some linux and install several nex processes on it. Anything better than a "VirtualServer" is OK to use.
Now about your problem in particular: I only know the routing to the host I run my server on. Try it yourself, servers are at
green.kicks-ass.net:26500 (26501), they are EU ladder servers. They'll run out on July 6th. Feel free to test them.
The reason why I bought that server was:
a) cheap price (18€/month, depends on server model of course) and you can order it for short contracts periods (1 month for example), and contract-extension is always done manually (so you don't buy a pig in a poke)
b) the server are so called RPS (acronym for "real" private server, see here:
http://www.ovh.de/produkte/rps2.xml). These are machines with real hardware (i.e. real CPU, e.g. Atom or Athlon, and also real RAM), but what is virtualized is the hard disk, which is at some other location on the globe. Reading and writing speeds are about 2 to 2.5 MB/sec. While this rules the server out for file-server usage, it doesn't matter for game servers. Nexuiz servers load up everything at the start of the map. Logging (which uses the disk from time to time) didn't cause problems in my case, I assume that the linux-kernel cached it just nicely. If you need stuff like server-side demos, you can use ram-disks (I'm doing that) to not lose performance, and save the completed demos to the hard disk in a cronjob later (that's how I do it anyway).
As you could figure from the port numbers I'm running 2 nexuiz servers. IIRC, the CPU usage was 30-35% for a full 3on3 CTF match on one server, so 2x3on3 CTF matches should not be a problem either.
HTH