As I said in the question - no fix I could find helped (including advise to click on the Apple logo on top-right of the screen in order to shutdown the computer and restart it).
The problem was that I had an external trackpad connected, and somehow it was powered on. Something was pressing it, so my trackpad click was always pressed and never released.