I’m not sure how you managed to do that, but I’ve restored the media deleted today back to your AnkiWeb account. It should start downloading on your next sync, but there’s a lot of it, so it will likely take more than one sync to get all of it.
Once you’re back in sync, consider running Tools > Check Media to delete your unused media.
There are a few possibilities for getting around that error –
Log out of sync [Preferences > Syncing] and then when you click sync again, you’ll log back in. That will force a re-scan of the media and usually clears up that error.
Another option [I thought of this just now, but I think it will work] – create a new (empty) profile in desktop Anki [File > Switch Profiles], and do a one-way sync upload to AnkiWeb. Then you can log out of sync there, switch back to your real profile, and do a one-way sync upload to AnkiWeb of your real collection.
There has been an issue lately after we restore media for folks, so if the re-scan doesn’t do it, we might need to have the dev fix your account on the server side.
As a last resort, you can delete your AnkiWeb account from your account settings page. That should free up your email address to create a new account and start syncing with that.