Technical Staff
Probably the most important aspect to consider when choosing a provider is the quality of their technical staff. The technical staff are the ones who will get your connection running to begin with and then keep it and the network running in the future.

Check the experience of their staff in TCP/IP data networking. They should have several people who have been running TCP/IP data networks for close to 10 years. The average experience is also relevant, as it's likely that you won't usually deal with their most senior people. However, it's reassuring to know that the very senior people are available if you need them. Make sure that their "technical" staff consists of people who are experienced with TCP/IP and not of people whose previous assignment was "networking related" and have now been assigned to this new project.

Make sure the provider has adequate staffing to cover the usual situations. If they send people to Interop for a week, how many people are back at the office running things and how skilled are they? If they only have a few technical people and they all go to shows, then what happens if your network connection breaks while they are gone for a week? (Be suspicious if they say they can handle it by dialing back in...)

Find out what their technical staff turnover is. If people are leaving, find out why and who is left to keep your connection operational. Many suppliers of service have single points of failure in their staff capacity as well.