Good rsync-with-version-history solution for mission-critical remote backups on Windows

I may be missing the point but have you considered using Robocopy on Windows. It is similar to RSync however you can't schedule it from the application directly.

This can be overcome by writing a batch file for the copy and then creating a Scheduled Task. Robocopy is free and extremely robust. I often use it to copy files between Linux and Windows using Samba and the network, and the resume capability of Robocopy is really powerful.

Is rsync smart/efficient at detecting which files to copy/delete?

Rsync is extremely efficient at detecting and updating files. Depending on how your files change, you might find a smaller number of large files are far easier to sync then lots of small files. Depending on what options you choose, on each run it is going to stat() every file on both sides, and then transfer the changes if the files are different. If only a small number of your files are changing, then this step to look for changed files can quite expensive. A lot of factors come into play about how long rsync takes. If you are serious about trying this you should do a lot of testing on real data to see how things work.

If the master crashes and a slave takes over for an hour (for example), is making the master up-to-date again as simple as running rsync the other way round (slave to master)?

Should be.

Is there any possibility of implementing multi-master systems with rsync?

Unison, which uses the rsync libraries allows a bi-directional sync. It should permit updates on either side. With the correct options it can identify conflicts and save backups of any files where a change was made on both ends.

Without knowing more about the specifics I can't tell you with any confidence this is the way to go. You may need to look at DRBD, or some other clustered device/filesystem approach which will sync things at a lower level.