Instant confirmations with pre-published, locked, transactions
This is a solved problem, see https://bitcointalk.org/index.php?topic=25786.0 and this.

It has also been recently implemented in BitcoinJ, and called "Micropayment channels".