I do some systems programming, so I had a clue as to what was going on, my first reaction was "PAE must not be enabled." Here's what's going on. With traditional paging, there is 4GB of physical address space available to a 32-bit x86 processor. This includes memory mapped devices, for example, your shiny new video card with 768 Megs of RAM takes up that much space of physical RAM your system can use. The solution is to use either PAE or PSE36, both provide up to 64GB of physical memory to a 32-bit x86 system. The limit of what you can map into memory at a time is still 4GB, but this allows motherboards to relocate the RAM that got displaced by hardware above the 4GB and still be usable.
However, it turns out that first of all, Vista automatically enables PAE if you want DEP since it is necessary for the NX bit. And in addition to that, Microsoft deliberately doesn't use RAM above the 4GB mark even with PAE for "compatibility reasons." The main issue being that DMA can't touch RAM higher than 4GB on x86. Microsoft could have easily had a special pool for this "high memory" in order to make some use of it when you know it's safe. This isn't impractical as the server editions of Windows are in fact able to use upwards of 4GB on 32-bit systems as well.
Linux has no issue using all 4GB of my RAM once I build my kernel with PAE support. Microsoft also claims that they support 4GB of RAM in their documentation. All in all, I find this whole thing to be a bit deceptive on Microsoft's part. Microsoft's solution: "Get Vista x86-64""