It was overheating - that's why it didn't feel hot by the fan - because the heat wasn't coming out, it was staying in!!
When I cleaned out the fan I didn't have any thermal paste to rebuild with - I've since applied some and yesterday the laptop ran for 15 hours without shutting down.
Fingers crossed, I think we've cracked it.