up-scaling is the way to do it. halving the size is going to save you crazy amounts of memory, and it should look okay. This isnt really a construct problem as much as it is a gfx card problem. textures take space, you can't have a crazy number, so you need to use them cleverly. like someone said, mix sizes. add effects and stuff to mask scaling, layer low and high res images to draw attention to detail rather than lack of it. you look amazing at art so you should be great at realizing what should and conversely what doesn't really have to be drawing attention. if you look at those ray man pictures, the backgrounds aren't pixel crisp. In fact they're FAR from it. people wont be playing your game because its "true HD" anyway. nobody really cares that much if they're going to be playing a 2d game in the first place. Anyway, the rayman sprites for rayman and the blue blob guy are SUPER crisp and vectory, compared to the brushy a very obviously scaled other stuff. i can see the upscaling artifacts on everything. In chris brobs' example this is a little more obvious because the black provides a sharp contrast, but in motion and juxtaposed on everything else its VERY hard to tell the difference between sharp and upscaled. the messier the art style, the harder it gets to tell. the palm trees are being reused at different scales with different filters in that image.
GIANT pictures are a bad idea. period. A game is not a painting or a video. a game needs to have huge vats of data ready to be accessed instantly at random. hence VRAM. ITS NOT developed enough to handle huge perfect HD images in a large quantity. Work around that. Limitations never stopped anyone from making a good game.