I know eservers.biz provides Windows2000 dedicated servers if you provide them with licensing information but they are out of stock on all servers. UnitedColo.com has Windows2k dedicated servers as well and they have servers in stock
Yes Rackmy.com is good for windows servers. Mike from rackmy is always helpful here , and from their posts i can know that their windows knowledge is indeed very deep.
If you are going to buy your own license then anyone should be able to install it for you. but its preferable to go with someone who can support windows ( having windows techs inhouse ) in case of problems, this is only if you are new to windows.
Managing win2k servers otherwise is not that big a problem. With the new windows update feature it takes care of basic security patches too.