I've been thinking about this and I like the idea of building the software to run on Heroku (or similar). For those that want a self hosted plan you just tell them where to host it and if they want installation outside of that you charge them a decent hourly rate to make it worth it.
I've always liked the option of providing a virtual machine image. Then you get a predictable deployment environment, and the client can run it where they like.
That only half solves the problem. A lot of shops that want self-hosted literally want to host it themselves, to keep data in their datacenters. if you built something deployable to EC2, you could make sure it works on a local Eucalyptus/OpenStack deployment or something. Or you could try to build for OpenShift and tell clients them have to have their own OpenShift cloud. But there's no real easy solution.
