Sorry for the delay, Chris.
Let me try and explain how this works and then maybe you'll see a hole in what's happening.
When you install SQL Server 2005, it runs on TCP/IP by default, port 1433, and allows you to connect with any Windows PC, using the standard ODBC dialogs. You connect using either the IP, the Windows name (+ /instancename if you use instances), or if you are on the console, then using "(local)".
SQL Server Express only allows local connections, meaning from the console of that server, by default, but the other editions should allow remote connections. However you need to check this using another machine. If the hosting company says they can connect from their workstations, not being the console, then that's not the issue.
When you connect with SSMS, SSMS is on your workstation and makes a socket connection to SQL Server, even if SQL Server is on your local machine. So you can't necessarily use SSMS to check settings on the server.
From what you're describing, it sounds like either they're a networking issue, or you are using Named Pipes by default to connect to a remote machine. Try opening the SSMS, typing in the address of the server, then hitting options. Manually choose TCP/IP to connect. See what happens.
alternatively, I'll try from here if you want to email me directly (sjones @ sqlservercentral.com). Set up a new user, or get the hosting company to change the password for a one time connect that you can change or remove after a test.
Follow me on Twitter: @way0utwestForum Etiquette: How to post data/code on a forum to get the best help
My Blog: www.voiceofthedba.com