Ok, I contacted Veeam support. This is what solved the problem:
When I created repositories, I picked my repository Windows server to be the Mount server. That was default option and it had sense to me.
Veeam Tech support suggested to change Mount server (right click on the repository and go to properties) from that one to the main Veeam server (server where I create backup jobs, restore jobs, repositories and where the Veeam console is). After the change I was able to restore the files. I did not need to wait for another backup cycle or to reboot the server. It worked right away.
I am not sure why this solved the problem, as I have Mount server (service) running on the repository server too, I have to understand better role of Mount server.