Yes, you should be fine to get 4GB of RAM - it mostly depends on your CPU. If you only have a 32bit CPU then you won't get above 4GB, and if you're on XP you won't get above 3GB. I would personally go with Corsair RAM as it's one of the top brands, but it certainly doesn't come cheap.

All signs so far are pointing to faulty hardware, but keep in mind that it may not be the GPU. Your CPU and GPU are clearly not overheating, so my guess at the next thing in line would be your PSU. What power is your PSU, and what devices do you have that are drawing decent amounts of power (drives, graphics, processor)?