How do "correctly" sync millions of files with rsync and inotify?

Solution 1:

Your case sounds exactly what lsyncd was made for.
It watches the directory with inotify and spawns an rsync with only the changed file(s).
It aggregates changes for a few seconds.
So when you make 5 changes in one second it will only spawn one new sync process to the destination server(s).