Wouldn't it be better to tie a phone number to an email address? An email address is still much more memorable than a phone number but the crowded namespace issue has already been solved. You could add something similar to an MX record to your domain's DNS that specifies where your "phone number server" is. The phone number server would be a simple database of username/alias and "real" phone number (although it could be expanded to do redirects, voicemail, 404s etc). The client making the call then consults this server which returns the number that it should dial.

"This is pretty cool because it means that anything that can speak DNS (pretty much everything) could have programmatic access to this data."

I don't think this offers an advantage over my solution, as any application that needs to use this will have to be modified anyway, the protocol I'm proposing would be equally trivial (or not) to implement.