Great news, and less great news.
@VJware - your tip about removing the config files was excellent, and post-removal I was able to mount the shared backup as a second storage device. I did an inventory and catalog and, sure enough, when I went into Exchange restore options for my server I found the old backup sets. Woohoo!
Sadly, the restore job failed.
"The job failed with the following error: Cannot log on to EWS with the specified credentials. Review the resource credentials for the job, and then run the job again."
I check to make sure my network share permissions were clean (confirmed - Everyone has full access).
Then I ran the Test Credentials function in the restore wizard and all my credential tests came back successful.
I tried running the same restore job a second time and got another failure:
"The job failed with the following error: A communications failure has occurred between the Backup Exec job engine and the Agent for Windows."
Honestly, I'm surprised to see a different error - I would have expected the same issue with EWS login credentials given that I was unable to find the EWS login credential configuration.
Any additional tips would be greatly appreciated!