Is there any way to make shortened addresses verifiable?

Right now you have to trust the owner of a shortener to not change addresses. Eg the owner of EVILB.TC might shorten http://evilb.tc/yourname honestly for a few weeks (or months, or years) then suddenly change the address (or all of them on the site) to one of his own.

Short, memorable names for Bitcoin addresses are great, but is there any way to achieve them without (or with less) centralised trust?

Note: I'm not saying that PAYB.TC is evil :-)