It's a fairly common problem, in most laptops the GPU is soldered to the motherboard. Heating and cooling cycles cause the GPU and motherboard to expand and contract (and possibly become warped) which stresses the solder joints. Overheating makes this problem worse.
The solder may crack or begin to separate from the motherboard, causing an inconsistent electrical connection, so the problem may be better or worse on a cold boot, warm reboot, or under load depending on how completely the affected connections make contact at different temperatures.
Sometimes it helps to put copper shims between the heatsink and GPU to keep the solder connections in place, but the permanent 'fix' is to either have the solder reflowed or reballed when possible or replace the motherboard.
Has the fan or heatsink on this laptop been cleaned?