OOM killer despite lots of free memory on PAE kernel
A quick google for oom killer premature seems to suggest there are a few reasons the OOM killer could be invoked even when the system has plenty of apparent memory/swap available.
One possible explanation is memory fragmentation, in particular:
Normal: 2386*4kB 2580*8kB 197*16kB 6*32kB 4*64kB 0*128kB 1*256kB 1*512kB 1*1024kB 0*2048kB 0*4096kB = 35576kB
Suggests that there aren't many normal large pages available.
I'm afraid this isn't a complete answer to your question, but it could point you in one possible direction of inquiry.