What to do when a SQL backup job created with SQL server Maintenance Plans fails with this error?

Investigate! No useful information in the logs.
Previously that day I dropped a few unneeded databases so maybe the Maintenance Plan was still referencing them. Everything looked good when the Maintenance Plan was opened in SSMS (it was configured to backup “SELECTED” databases), I could not find any reference to the deleted databases. Under the hood, the Maintenance Plan was still trying to backup those deleted databases because when I clicked OK and then hit Save, that Maintenance Plan was refreshed and everything worked just fine.

So always try to find the root cause.