Hence the suggestion of a switchmode regulator 
Something like the Maxim MAX787, does 5volts at 5amps with a fairly small number of external components.
Of course, finding a power supply that does 12v at 2amp and 5v at 5amp to begin with would be a lot easier!
I'm now considering two separate switchmode power supplies, built into a smallish jiffy box
I see, the max787 is interesting. i notice its been discontinued,but is still not too hard to find. I looked at the data sheet but it doesn't seem to show much about what kind of heat it dissipates at full load. Of course it will not be anything like a linear but i suspect pushing it near 100% might make some nice heat.
finding a laptop style psu that does 12v/6A+ is easy(they use them for under kitchen cabinet lighting actually),i would think 6A would give you 5 for the machine and then 1 amp at 12v...not counting losses.. not sure how you would get the -12(although its trivial and even a negative linear reg would do for the measily .3A).. not sure if there would be any backlash with all this stuff sharing common rail for ground etc.
also, the weight you mention on the 500psu,do you have the switching style or the old transformer style? the switching 500 psu's were pretty light and still do 4.5A.. i realize you want smaller size but short of the desktop psu i mentioned like i built originally,its going to be hard to save space,and you will likely need big heat sinking.
I wonder how hard it would be to do a design similar to the stock 500 switching psu but use nice fets with low rdsOn values and maybe up the frequency for a even smaller xformer and reduce the size a good bit? no small feat i guess and probably no where near the effort.
If you do build anything keep us posted,and ventilate the case well
