After a little bit of Googling I found
this site. But, I also have no idea about anything w/r/t renting server space. If this is affordable, if this is a good rate, or anything like that. Also, the domain is .de so it seems to be German, but it's all in English and the prices are in both Euro and $.
I also found
this one, but, again, I don't know much about this stuff. This one is definitely less customizable of an offer than the earlier one.
One thing is that if you do wanna get something like this where the map size is figured into the price, you may wanna go in with mcedit and clip off parts of the world (after saving a backup, of course) which were generated b/c people got lost and wandered away--since there's likely nothing special built there and will probably never have anything built there. There used to be a mod called "tether" or "leash" or something that kept all players within a set distance (1500 blocks or so) from spawn. So the world was kept to a small, circular size. i don't know if there's been a new version or what, but that may be worth looking into, too.