MacOS – What does “mds: (Error) Volume: Could not find requested backup type:2 for volume ” signify

It's not an answer to your specific intermittent failure, but I do have a workaround that several clients have used.

I make them another account that isn't file vault protected and rather than logging out and leaving the mac at the welcome screen, enter the empty user and walk away. (or kick off a backup and then walk away)

In practice I get better backups when a user is logged in.

If this needs to work for you, do file a bug with apple since it should work each time and every time without a workaround. When it fails, there should be detailed enough logging to fix issues if they arise even if normal logs are suppressed as a compromise to added security with FileVault enabled.

Also BackupLoupe is great for poking at backups to see what is actually changing after the fact rather than guessing from logs and byte counts stored in logs.

I have had other people reconsider file vault and just use encrypted disk images for data that needs to be secured which minimizes many of the drawbacks of having the entire user folder inside file vault. I've done this myself since soon after file vault came out and I much prefer it compared to living with FileVault.

I had the same problem after first upgrading to Lion. I erased my Time Machine and it seems to work fine now.