when was the last time you changed your thermostat? if there is still one. it might be corroded or sometimes it opens sometimes not. since you mentioned that your fans are ok.

also when was the last time you changed the whole coolant/water combination.