Notebook overheating issue resolved, Again!
Well it amazed me that this is a typical issue. My Toshiba M400 the other day was running really warm during normal use, 60° C-70° C.
So of course I had to take the whole thing apart and inspect. The first thing I did was to clean out the FAN, again a big yuck! Then I took off the CPU fan and heat sink and removed all the old CPU paste. I then cleaned the surfaces with Isopropyl alcohol, re-applied some new thermal paste, making sure that it is evenly coating the CPU and then re-assembled the notebook.
So now my idle temperatures are more inline with when I got the notebook, 35° C-45° C.
Here is a good article I found on the topic.