Where are short URLs stored and how can I edit them?

You can update existing short URLs, if you have the appropriate privileges, by using the regular URL Shortener user interface and specifying a new short name. You can also directly edit / delete the existing entries, which are stored in a hidden list in Central Administration.

           http://<your_ca_server>/Lists/Muhimbi%20Shortened%20URLs

Do not edit or delete the first entry in the list.