That did the trick! Thank you very much.
In fact, it's enough to have:
Option "ModeValidation" "NoXServerModes"
After this xrandr shows:
1280x1024 60.0* 75.0
1024x768 75.0 70.0 60.0
800x600 75.0 72.0 60.0 56.0
640x480 75.0 73.0 60.0
Exactly what I need.
So it seems like the nvidia driver incorrectly validates the list of pre-defined X-Server modes? Since my monitor tells it cannot do more than 75Hz, and I also tried to explicitly limit the vertical refresh frequencies range with the "VertRefresh" option, and it did not helped.
Let's hope the developers will fix this in later releases.