Long story short. I ordered a new PC (Core2Duo E6550) back in December with it being shipped built and tested for me.  I have noticed that the past few months my performance has been terrible, constant reboots.  I couldnt play a 1080p movie which with my setup I should have no problem.  After a ton of researching I looked into the temp of my cpu. It was running at 85-95C when IDLE.  
 
I looked at my heatsink and to my surprise one of the pins wasnt even screwed in. The other 3 were barely screwed on.  I re-attached correctly and now my cpu runs at 25-32C. Performance is WAY better and I can watch the same 1080p movie flawlessly.    
 
My question is:
Is there a chance I permanently damaged my CPU because I was running with practically no heatsink for 3-4 months? I dont notice any problems so far but I am worried about the long-run and possibly the cpu note performing as best it could because of damage. I am going to try and get a CPU replacement from the company i ordered from since they didnt install the heatsink correctly, but I dont have hope in that.
 
Thanks.
John

The CPU slows itself down and will even stop as it overheats, in order to protect itself from damage.  As long as you are not planning on OCing it, I would expect the CPU to last at least the 2-3 years you will still be using your computer.

I was very 'lightly' thinking of attempting to overclock.  If I attempt to overclock now, is there a chance to causing permanent damage?

Since your CPU already runs at 1333MHz FSB, it's not a good candidate for OCing.  OCing will of course increase the chances of damage to the CPU, but if you don't boost the voltage, you are still unlikely to see any problems while you own the computer.  I'd suggest reading the various overclocking guides here and at other sites, then do some research into what CPU and MB to buy based on your OCing goal.

Unfortunately the best thing to have done is have them to fix the cpu/heatsink issue.  Its a good chance they would have reseated the heatsink, tested it and gave it back to you with the same cpu if it ran correctly.
 
If its running fine now it will likely be fine.  Are you planning on this being a machine you use intil it dies or are you someone that replaces a pc every 2-3 years?
 
At this point theres nothing much you can do.  They wont replace the cpu unless it doesnt work.  If it runs fine then I would say dont worry about it since they most likely wont replace it anyway.  Go ahead and try to get a replacement anyway to see what happens.
 
May the force be with you.

I already read a bunch of guides to OC'ing. In fact I found a few on my exact cpu in which they were able to overclock it to 3.2+ghz. I wont go that extreme. I was thinking of upping the bus to around 400 to get a clock speed of around 2.8.

Problem is with Intel push pin design. They have a tendency to come loose from rough shipping.

20% OC doesn't sound "light" to me, but go for it if your MB can handle the 400MHz FSB clock.

I don't think heat causes permanent damage, but can reduce lifespan.
 
Thats all you need to know, the same with OCing.