Kevin you are right.
In our case the problem was caused by having 2 cloned servers, a development and a production. Both were monitoring the same mailbox and both had their cron jobs setup. But the development server is not accessible from the internet, only locally.
When a ticket was created by email-to-ticket, each OS instance was monitoring the same mailbox and was creating it's own ticket and notified the ticket creator (which got 2 tickets, one from the dev and one from the live, with different numbers). However, the ticket creator browser, only knows the live server address, and can only access one of the two tickets created, that on the live server. Trying to click on the dev server ticket link in the autoreply email, links the ticket creator to the live server with a ticket number that does not exists in the live server, but only in the dev.
The problem was fixed by commenting out the cronjob line in the dev server and disabling email fetching options on the dev (plus autocron).
I hope the answer will help someone with the same problem.