To OP,
I think you've got a great kernel of an idea in this question and I'm glad /. posted it up. Let's turn this into a high level RFP shall we?
First a bit of background:
I've stopped at every point along the spectrum of data ownership for my personal and business (it consulting (Known Element Enterprises) and mesh network non profit startup (Free Network Foundation) data:
1) most (legally and maybe physically, but that's debatable) safe option of running compute/storage/network gear at my house (in Los Angeles). Single grid/point of entry for power (run to a dedicated sub panel naturally), single net uplink (DSL, homed to the CO two blocks away, fiber to same CO available for me to cross connect if desired)
2) Using shared hosting at HostGator (while employed there as a Linux admin)
3) Using various VPS providers (MediaTemple while in Los Angeles and knowing numerous admins who built out the environment, HG while working there)
(previous two options were due to moving to Austin and not having a house like I did in LA). Started out with shared hosting, moved to VPS when I needed OpenFire,OpenVPN,Chili etc. Basically moving beyond simple PHP apps.
4) Having the gear that used to be hosted at my house placed into Joes DataCenter in KC MO and maintaining a fantastic relationship with them. I added Cyclades ACS48 and PDUs for full OOB access/management.
So I have firsthand experience with the full spectrum. From full management/control/legal protection, to fully outsourced managed hosting, to hybrid model (colo).
RFP framework
1) Willing to treat the hosting package as truly business critical and able to pay accordingly (100.00 to 300.00 a month base, reasonable per user/per month charge).
2) You want this to be a turnkey (ala Google apps) solution, with things like zero backup window, live migration of state in the event of failure, redundant switches/routers/drives etc. All very doable with ZFS, open source virt flavor of choice, x86 servers, 10/100 (2950 et al) Cisco switch hardware off the gray market (to keep costs down)
3) You want encryption of everything so that even in the event of a NSL, you'll be protected. You have some sort of key management system in place to handle the private keys that are generated. Look at startssl for an example of how they do things. They use client side SSL certs for all auth. It's quite slick.
4) You are OK with a single facility and remote snapshots (ie hot active/cold standby). (Maybe the hot site is in a reliable colo, the cold site is s3/ec2 with the various issues that entails).
You'll be willing to pay a premium for hot active/warm standby) if a particular client requires that level of recovery.
From the above, I'll let others expand this and see if the community can put an RFP together for hosting companies.