The random errors with Access and 2K3 server sounds more like bad coding than a server issue to me. Random errors don't just "occur" with something like that, and Access is a little more susceptible to that sort of thing.
Anyway, having said that, check out my boys over at
Sectorlink. I've got a Win2K dedicated box with them, and have been with them 3.5 years. They know their stuff, they kick ass, and they're never down (at least they haven't been on me since before the blackout of 2003).