I think one thing that could be added to the list is flexibility, especially in billing. When stuff happens, as it often does, how flexible is your provider? For instance, can they or will they set back billing, if requested, if you encounter delays shipping your servers for colocation? One other consideration is your provider's backbone connection to the Internet. For example, do they use BGP? Do they have failover solutions? Do they have GigE?