The random "a"s everywhere is a big sign that something isn't right, and all the random characters flooding the screen. This doesn't look anything like a software problem! If the RAM is fine (MemTest assuming it tested correctly thinks the RAM is fine), it could be a more serious issue (CPU problem, GPU problem, cache problem, VRAM problem, etc). I doubt the video card is even utilizing the GPU or VRAM at such a low level like MemTest so that leads me to think it may be a problem with the CPU. If you have a removable CPU and you can get to it, try reseating it, same with the RAM. Also if you have any sort of miniPCI/miniPCIe cards, reseat those.
The issue I was referring to with the overheating suggestion was that I overclocked an old computer one time (granted, it was a Pentium 1) and I got weird symbols all over my screen when booting. I don't think it was overheating, but the CPU was definitely having problems. It didn't have any problems after returning to normal speed. If you can underclock it, try that, though it's probably not an option on a laptop.