This could also be done with the Raw Transactions capability of the Bitcoin.org client v0.7 and higher, and thus eliminate any concern over sending a customer's private key to a third party service.
The only thing that's missing is a lack of ability for bitcoind to find which txids belong to a specific private key. There is no index on that, so the only way for this to work is for it to scan the whole block chain looking for such transactions. Pieter Wuille has mentioned allowing such an index to be optionally created, but I think that mention was more recent than 0.7.
If that index existed, then the
Sweepprivkey proposal I made over a year ago would be a slam dunk. I'm hoping the index becomes an option sometime soon, because the power to pay with private keys anywhere would open up new avenues for business I don't think have been considered.
On the other hand, Blockchain.info presumably maintains that index (given that they can scrape all coins off a private key instantly).