I have found solution today on a call with Salesforce Support. I use MS Outlook as email app. It has a 'Safety link' feature which opens internally a link before you actually click it. Salesforce 'Verify Account' link is meant to be one-time, so if MS Outlook opens the link before you open it, when you open it in a browser it is considered as second time and doesn't allow you to login and setup your password and security questions.
So the solution is either use a different email app, or copy the Verify Account link and open it into an anonymous browser window to prevent any conflicts with other Salesforce user logins. This solution works as a charm.
However, if you have already clicked the link, there is no other way to restore access except contacting Salesforce support.