Thanks a lot for your suggestion.
I actually tried it before my original posting, but to no avail.
However, I seem to have found a workaround: when I upload the entire Templates folder (which contains the Includes folder, which in turn contains my changed Navigation.ss file) SilverStripe recognizes the change and takes it into account during the rebuild, and I do see the change in the front end. Note: this is not the case when I upload the Includes folder only - it has to be one level higher (the entire Templates folder)!
I did several tests and they seem to confirm this rule.
Now I investigated a little trying to understand the mechanism and here's the only conclusion I could find:
It seems SilverStripe is checking for changes to the files in the Templates folder (or specifically Page.ss if you use the standard theme - in this case Page.ss is the only file there)! If the content of the Templates folder appears unchanged (and that's the case, at least under Linux, when you update a file deeper in the folder's tree) then SilverStripe stops checking for changes, instead of doing a recursive lookup throughout the entire Templates tree...
Weird but that's the only explanation I can see.