After restoring my iPhone XS Max, Im asked to enter a password to unlock my backup. Ive tried every password I use to no avail. Help?

You do not remember your encrypted backup password, I can understand.

You do not remember having created an encrypted backup, I can understand this also. (This is not true in your case)

This means the iCloud Key chain was checked while creating the encrypted backup because by default it is checked.

Look for it in the iCloud Keychain.

Did you un-check the keychain while creating the encrypted password (By default it is checked) See the pic hereunder.

If you had un-checked then the only option that you have is, keep trying various passwords as there is no limit on the number of attempts.

You may have been given this option as given in the pic below whien you had first synced your iphone to iTunes/Finder. You may have checked "Do not warn me again"

You may have forgotten that you had entered a password. --> About encrypted backups on your iPhone, iPad, or iPod touch ...