Tom, I completely forgot about another backup program that I've used before: Genie Backup Manager Pro. It seems to be capable of everything you're looking for. NAS, encryption, VSS, etc - I'm not positive about the others but I believe so. It's $70, but at least it's a one-time expense.

I've mostly recommended it for my clients who are frightened by the cloud, even if their data is encrypted before it goes up. It appears that the primary difference between Genie's Home and Pro software is the ability to encrypt (at least, I couldn't find anything that indicated the Home version would encrypt the data).