The client database records tags using four different statuses:
current (tag exists on service)
pending (tag will be uploaded to service)
petitioned (tag exists, and a petition for its removal will be sent to service)
deleted (tag was once on service, but no longer is)
Deleted tags are usually hidden, but you can see them on the manage tags dialog by clicking the 'show deleted' checkbox. They are written in the form '(X) tag'.
You can delete current tags (converting them to deleted tags), and you can obviously forget pending and petitioned tags from the 'pending' menu (which will respectively entirely forget them or return them to current), but there is no way to forget a tag's deleted status. 'clear deleted record' means to do this–to tell the database to delete any rows that record a tag as deleted, making it as if it had never existed. It is a debug method I wrote for myself, really. I expect you might only use it if you are screwing around with SQLite and tag archives or something.