After a closer look I noticed that indeed a couple pins were a tad bent. Moreover, I realized that I had not used the little lever to secure the CPU previous time, so I'm not even sure how it was working like that on the 1st place.
Then to make matters worst, when I put it back, I just assumed that it was sitting ok (while it was not), and went ahead and used the lever on the cooler, which as you know, puts a tremendous physical pressure on the CPU (to keep it in place while having most possible contact). Either way, no doubt I ruined the CPU, and chances are, the CPU socket in the motherboard.
Nevertheless, I did proceed as if there was a chance, placed the CPU the best I could (while the socket's lever was up), then closed the lever. Cleaned the old thermal paste, put some new one, placed the clean cooler back. And started the pc. Same situation.
What sucks too, is that I don't have another CPU to check if the socket is ok, or not. And I'm certainly not going to buy another CPU just to find out that the socket IS ruined too.
I guess this pc is good for parts now :(