Sorry joiseystud, I tried to reproduce the problem, but could not do so on a test environment. I am facing this problem on a live website that I did not develop. I am just maintaining it currently. We upgraded from 4.9.4 to 5.6.2 recently.
I dug out a backup of the 4.9.4 version and went through the upgrade again on a test server. The upgrade does not seem to affect the links on the test server.
I compared the web.config files for the test app and the live website, but they look the same.
I was hoping to get some ideas or some "requirements" for proper functioning of the LinkClick handler, e.g. the web.config section that Cristian quoted. I have no idea how it works internally and what could affect it.
Thank you for your time.

Thanks for the suggestion, Justin.
Unfortunately, 5.6.3 seems to have issues of its own. Additionally, I cannot reproduce the problem on a test server. Hence I cannot try out the upgrade - to check if it helps - before applying it to my live website. In my situation, upgrading sounds risky. On top of it, my website takes about an hour to backup. and an equal amount of time for the restore (if something goes wrong). I have to be very careful about bringing my site down for such an amount of time.
I might try the upgrade after 5.6.3 is more stable.
Thanks again!

Thanks for the guidance.
Why didn't I think of that before! :|
Well, I did bring down the set to the test server. Sadly, it doesn't work there either.
I upgraded to 5.6.3. Still the same.
I would like to download the source and step through the request next. But my post here never got answered :( I am not sure how I can place source code in an existing application and step through it. Have you ever tried anything like that?