Heading 3, not Header 3
What is the difference between headings and headers?

This has nothing to do with your TOC updating or not.

You cannot delete the Heading 3 style from a document. Word will not allow you to do that. All that has happened is that it is not appearing in the Quick Styles Gallery.

You should be able to apply the Heading 3 style using the keyboard shortcut Ctrl+Alt+3 regardless of whether it appears in the gallery. Heading Style Keyboard Shortcuts Add-In for Headings 4-9

See:

• Understanding Styles in Microsoft Word
• How to control the Quick Styles gallery on the Home tab in Word by Shauna Kelly
• How to create a table of contents in Microsoft Word by Shauna Kelly

When you say that you cannot update a table of contents, what, precisely, are you doing to update it. What do you expect to happen? What happens instead?