The Bitcoin.it wiki article about proof of burn mentions "verifiably unspendable addres" and this method has been used by Counterparty to create XCP.

Is it actually possible to create an address that is "verifiably unspendable"? If yes, how? Or does "verifiable" just mean extremely hard, the way it is extremely hard to find a private key for any public key?

Or in other words: Are there valid Bitcoin addresses for which it's possible to mathematically prove that there is no private key?