Is it actually possible to create a "verifiably unspendable" address? 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?
Every valid ECDSA public key corresponds to some valid ECDSA private key.  Bitcoin addresses are not actually public keys though, they are a 160-bit hash of a particular binary representation of the public key.

You asked:


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


As far as I know, the answer to that is no.  To construct such a proof, you would have to somehow consider the enormous set of all possible public keys, and prove that none of them have a binary representation whose 160-bit hash would match the Bitcoin address in question.  The point of hash functions is that they cannot be easily inverted, so you can't just get a list of all the valid inputs that would result in the same hash.

The number of ECDSA public keys (approximately 2^256) is vastly greater than the number of Bitcoin addresses (2^160).  So the average Bitcoin address actually corresponds to about 2^(256-160) = 2^(96) different public keys.  So it seems like it would be hard to find an address that corresponds to 0 public keys.