You still haven't said what subjects you shoot. It does make a difference. Leaves vs architecture vs animals vs people - it all makes a difference on how big you can make a print. (Edit: Posted as I was)
Fact is, sensor size is not the only determining factor printing large images. I'm not sure who pounded that garbly goop into your head, but it is incomplete and lacking information. Lenses you are using, the Iso, exposure, subject, tripod vs handheld, paper, ink, Jpeg or Raw, home printing vs Quick print shops (kinkos) vs professional services all make a difference. If any one of those things are off, it would be easy to incorrectly blame the camera.
Perfect Resize, Alien Skin's "Blow Up" and I think Topaz has one too, are all programs that can take a even 10mp image and create enormous prints (larger than your 4'x6') with little noticeable detail lost and is something you should look into. I have seen these programs used on 10mp images and blown up to wrap semi truck trailers. The software is also a hell of alot cheaper than a camera. I don't know of anyone who doesn't use one of those for large prints.
And your math is off. The difference between 12mp and 24mp is only 25%. 25% wider, 25% longer on each side. Note that the D600 is double the resolution of the D70s with a 6mp sensor. That would be 50%.
To illustrate by your standards you have set, a D800 will not do what you want. But the rest of us know, that even your current camera will will easily make a poster print.
Native Print sizes:
D70s 6mp = 3008 x 2000 /300dpi = 10.03" x 6.67"
D300 12mp = 4288 x 2848 /300dpi = 14.3" x 9.5"
D7000 16mp = 4928 x 3264 /300dpi = 16.43" x 10.88"
D600 24mp = 6016 x 4016 /300dpi = 20.06" x 13.39"
D800 36mp = 7360 x 4912 /300dpi = 24.54" x 16.38"
Like I said, I have seen 10mp images resized to 15' x 20' that looked great and used for advertising and their high standards. A lot of work went into it, but it can be done.
Of course you can always stitch images as well - But you haven't said what you shoot so I'm not sure if that would work for you or not.
I could put more but check out Thom's info on printing. I have have it bookmarked and he goes through more details that are factors in printing and to keep in mind.
http://www.bythom.com/printsizes.htm
Point being, 12mp, 16mp, 24mp will all do what you want. The camera you choose isn't going to matter. Really what it comes down to is how much you want to spend.
I ignored the last paragraph since it had nothing to do with information that was helpful to the discussion. I'm bowing out from this thread.