So, after finding this page on the internet:
http://www.laptoprepair101.com/laptop/2006/01/04/toshiba-laptop-overheating/
I decided to take my laptop apart to see if there was anything obviously wrong with the cooling solution. The first time I noticed the fan was covered in dust; I cleaned it with compressed air. But this didn't seem to make much of a difference.
I then removed the fan and noticed that the thermal interface material seemed really 'worn out'. i.e., it was spread thin on the CPU, and there were solid chunks around the surface of the cpu, where there is no contact with the heatsink. So I wiped it all off and put some coolermaster compound I had used on my desktop PC.
The result was obvious: 60C idle, and a max of 73C with both cores at >50%.
The other thing worth mentioning is that I noticed that keeping the laptop lid closed when it's on the dock 'traps' the heat, and raises the temp by a good 5C. So now I make sure I always keep it open.
Hope this will help anyone else having the same problem.
I'd still be interested to know what other users temps are , for comparison.