Thanks, Auto Doc.
I did all that and more. I actually adjusted the clearance by the book, with the piston 1/4" (6mm) past the top dead center. While it is possible I may have been off by 1/16' or 2mm on the downstroke, I doubt that should result in what I am experiencing. I strongly doubt everyone who has succesfully adjusted the valve clearance is that surgically precise...
As ILENGINE pointed out, the clearances I gave in my initial post were in mm but the screenshot I attached shows them both in metric and imperial.
Since my original post, I have re-opened the valve cover and checked the clearances again. They were still in the spec range, I did not get them wrong the first time and the nuts had not loosened. Both times the engine was cold.
So I still do not have an answer to the problem. If anyone has any ideas, please share. It is still hard to start and tends to lock. Yesterday it took even longer than usual, about 10 seconds, and I do not know if the longer start was random or an indicator that it is getting worse. By the time it did start, there was fuel sprayed and dripping out the exhaust... I might be tempted to blame a spark plug that acts weird when cold - I will replace it, although it is new - but that still would not explain the engine lock, hence my original post.