Problem solved, thanks to Stefano's spot on analysis.
In my case, when I inserted https://<my-domain>/path links on my newsletter, and sent a test email, it was converted to http://<my-domain>/<tracking-code> inside the email.
Turned out that on my site's Global Configuration, the site address was still with http://. Turning that to https:// and the test email now comes with https://<my-domain>/<tracking-code> and the link works. No more "URL not verified" error.
So, the test newsletter used the configured site address to compose the link on the email message. The webserver is configured to rewrite all http requests to https, so it messed all up.