Is VSS 5.0 compatible with a 4.0 database? Do I have to upgrade all users to the new version? What about 6.0?

For 5.0 vs. 4.0 compatibility, read KBA Q176553 • Version 6.0 can read and write 5.0 databases, and has an option to upgrade or use a new database format. Using this new format gives you the new label promotion feature, but cannot be read by anything earlier than 6.0 (You’ll have to upgrade everyone if you want to use the 6.0 database format). There are also some performance enhancements with the new 6.0 version of the database.