Have you tried running an inventory on your tape device or library?  This updates the database as it seems there is missing records.

Also check this forum post which deals with this message and has a solution - Cannot find record in table tapestorages.. - R&D Forums (veeam.com)

Hi @mvillares -

I just wanted to follow up and see if you’re still having an issue with Tape Backup Job? Did Chris’s comment help you resolve the issue? Don’t hesitate to reach out with further questions if your’e still having problems.

Thank you.