Dedicated servers are servers you rent or lease in someone else's rack in their data center. You get a particular class of machine and a particular amount of bandwidth. You can have it administered by the data center people, or you can be the only one with root access.

An example of dedicated managed servers is [htttp://rackspace.com|Rackspace]. They specialize in managed dedicated servers. It's all they do. The admin for the box would have access to your data, but Rackspace hosts for the US Marine Corps and many other highly sensitive organizations.

I'm not sure who to recommend for dedicated, unmanaged servers (ones you'd manage yourself with no other root users).

Another option is server colocation. That's what they call it when you buy the server, ship it to the hosting company, and they put it in their rack. You're paying just for rack space, power, and bandwidth. All the people do to your machine is physically secure it and reboot it by power cycle when you ask. They still have physical access to your machine, so it'd have to be someone you trust. Hurricane Electric does lots of colocation.

Perlmonks itself is hosted at Pair Networks. I've yet to use them myself, but I hear good things about them. Their site says they do both managed dedicated hosting and server colocation. Their site does a pretty good job of describing the packages they offer, too.

There are lots of other companies you could contact about either dedicated hosting (managed or unmanaged) or colocation. The above are just examples with which I'd be comfortable doing business.

For the ultimate in security, you really want to employ your own sysadmins and network techs and run your own data center.