Evernote Rescue Project was a success

Just as I thought: my Evernote experience has improved noticeably by deleting the hundreds of tags with 0 or 1 note associated with them.

The trick was deleting the tags in smaller batches of 10 to 20 tags at a time. Evernote reindexes and syncs after each deletion and deleting too many tags in one go slows Evernote down dramatically.