I will look for a company/network which is at least as good as SoftLayer but allow colocation. If you know any, let me know.
How is that different from any co-location provider that already exists? Every co-location provider has space, cooling, redundant power, and a number of various-quality back-bone/ISP providers available on site. They won't be any different from what SoftLayer does. Just pick any reputable co-location facility in each of your regional centers. The draw-back with co-location is that you have to actually have boots on the ground in that city, though. Another option is "fully managed" services, where you tell the data center staff what to do. Costs more, and the data center staff is not focused only on your application, but it avoids having to hire people all over the world.
There are a variety of managed hosting providers: <a href='http://www.digitalrealty.com/'>Digital Realty</a>, <a href='http://www.rackspace.com/managed_hosting/configurations/'>rackspace.com</a>, <a href='http://www.peer1.com/managed-hosting'>peer1</a>, <a href='http://www.business.att.com/enterprise/Family/hosting-services/enterprise-managed-hosting/?GUID=2DE4A87A-A621-41A9-B598-E7C8787B5224&WT.srch=1'>AT&T managed hosting</a>, and many more.
This is my point: all the back-haul goes across the same wires. My expectation is that it wonn't matter much if you let the user's ISP figure out how to get the packets to your central data center, versus if you let the user's ISP figure out how to get the packets to your regional data center, and your regional data center then figures out how to get the packets to your central location, as long as the user's ISP is big enough to have reasonable peering agreements with all the big carriers.
For the average case, going into your regional center and then back out again will likely just add a little bit of latency.
In some degenerate cases, an ISP may have its own back-haul, which it oversubscribes and runs on a shoestring, and it might prefer to try to send the user's packets through its own wires to the nearest IX to your central server. In that case, re-branding the packets onto peering exchanges that you pay for may improve quality. I would expect the share of customers where this matters to be significantly less than 10%, though -- that's an expectation of mine that seems to be significantly different from your expectation. You seem to expect that this will be the common case. If you actually get hard data on this (in any part of the world) I'd be very interested in seeing the actual outcome!
I still think the real quesiton is whether the additional services will be worth it and will gain traction, so I still suggest trying to figure that out, within a single data center, first.