Hi Walz
I had a A300 and an M300 that both did the same thing. Cleaning the dust out would have helped with overheating the GPU, but that is apparently not the case. In my case the problem was that the GPU chip had overheated and then cooled after use so many times that the solderballs connecting the GPU to the motherboard were no longer making a good connection. I had to remove the motherboards and using a heat gun "reflow" the chip back into position. Most people would just buy a new Laptop...
Another possible cause could be the physical cable that goes from your motherboard to the LCD screen may have been damaged (overheating and bending can cause cracks, In that case you would just need to replace the cable...
I recommend you download Furmark and run a couple of tests to see what temp your gpu is reaching. If it is not overheating it could also be your Video Ram that is faulty.
Just throwing out some ideas here but if you are not comfortable disassembling your laptop I would take it to a local shop, but try to ask around first to get a good one.
p.s. The same GPU problem occurred on 2 of my IBM t41p laptops, AMD GPU's needed to be "reflowed" (could only get one working).