unobstructed = dusted out as well? I really dislike laptops that don't let you get to the heatsink / fan assembly, so if that's not an option for you, and dusting it out hasn't proven to help, you're permanently stuck to using a cooling fan table accessory or get brave and see why the fan is having issues keeping the system cool.
Things like this can help out as well:
http://www.amazon.com/Belkin-F5L001-Laptop-Cooling-Pad/dp/B000NWIOM6