Or create a directory that displays all recorded external IDs?
when you click in the QuickSearch (white search box very top left) you should see a drop down of 'what do i want to search for' and External ID is in there. So you can select that and then just enter the Ext ID that you are looking for. You can also add the Ext ID field to a Profile which you have set up for Search or Listing if you want this more public eg I set this up on demo.
This link for a user to 'edit' their own (which you wouldn't want I guess ;-) but you may need to check if that url is available and set the field to View Only http://d46.demo.civicrm.org/civicrm/profile/edit?gid=16&reset=1
This to 'view' it http://d46.demo.civicrm.org/civicrm/profile/edit?gid=16&reset=1
This to 'search' for it http://d46.demo.civicrm.org/civicrm/profile?gid=16&reset=1
And this (or may be another url for this) to View the listing http://d46.demo.civicrm.org/civicrm/profile?_qf_Search_display=true
External ID is also available from Advanced Search and Search Builder like most other fields.