... As I see it, PPS makes the most sense because old, unlucky work will essentially be getting less and less valuable to work on as partial matches rack up. This will turn into "pattern hopping," although I think I could partially avoid that server side (not allow miners to submit matches for just any pattern...). That doesn't really jive with my idea of this as a free market place though. The point is that requestors can set any price they want, and miners only have to work on it if they think the reward/difficulty is high enough.
With PPS, we can have the requestor lose N*PPS if they cancel after N shares have been submitted. ...
With the existing vanity pool, neither the customer nor the pool operator bear much risk. The risk belongs to the vanity pool miners who may toil for no reward or who may get a lucky break and a big reward. The goal of your project, as I understand it, is to reduce the risk to the vanity pool miners. You've done enough math on the forums and on your own Web Site I'm sure you understand the risks that a Poison Distribution brings to a PPS pool operator. If you can handle the risks, I agree that PPS does make the most sense.
Another option is to shift the risk to the customer requesting the vanity address. When the customer's funding is exhausted, miners won't work on the customer's vanity address until more funding arrives. If a miner finds the solution early, you would refund the unused funding to the customer. Other variants might be to allow your customer to specify both the total funding and a fixed PPS or to specify total funding and PPS as a fraction of remaining funding.
I hope you *do* allow pattern-hopping. My version of the vanity mining client is customized in several ways. One customization is that I will not submit work that I consider to be too cheap. Even if one customer with a common public partial key has a collection of work that can be performed simultaneously, if the value of certain vanity addresses within the collection is *too* cheap, I won't submit those. (I'd rather pour out my milk than sell it at a price that's too low.) In turn, I evaluate the value of the collection of work differently than the standard miner evaluates the collection of work. Thus, my preferred pattern is often not the same as the standard miner's preferred pattern.
If you implement PPS and pay as shares are discovered, you could probably implement your project with no changes to the existing vanity mining protocol. Just make sure your site offers shares (5- or 6-character shares, perhaps) to any oclvanityminer who comes knocking. For transparency, your Web Site should show the true (7- or 8-character) vanity address being requested along with total funding, and PPS formula. But the mining client only *needs* to know what it will be paid for.