About the resolution/scaling:
nubie's rendition is what I figured to be the most useful mode. It can also be done side by side scaled to fit. This doesn't really look that bad - GBA emulation on PSP is usually scaled + bilinear filtered, and while it does look blurrier and more washed out it's generally more than good enough to be considered worthwhile. With pixel shaders we can possibly efficiently implement custom filters such as bicubic filtering that look better. Another mode is just showing one of the screens (for games that don't really use the second), and for the few games that actually do depend on vertical orientation (ones that treat it like one big screen) it can be layered, which will look small but still be quite usable. All the extra space can provide touchscreen UI if desired.
About feasibility:
I expect Nintendo DS emulation to require roughly 4-6x what GBA emulation does, although this will vary tremendously per game. Bear in mind that gpSP on GP2X is not really representative of the best GBA emulation you can get on ARM, I'm sure it can be optimized quite a bit over that (even what I have now is significantly faster than what's out). A lot can be done in just making the CPU and GPU emulation faster without resorting to more exotic tricks, although using the MMU to accelerate things could help a lot, even w/o hurting Linux (as some discussions here have shown).
Some considerations: a lot of games probably put the CPU in idle state a lot, especially 2D ones. Consider that a number of games may in theory actually need less CPU on DS than on GBA because DS has more acceleration for audio (much of the CPU time on GBA games tends to towards audio rendering). A lot of games don't really use one of the screens for important things, and could be frameskipped more heavily on one screen without it really hurting the visual experience too much.
I'd love to see the C64x+ DSP used for fast/accurate 2D rendering, the PowerVR used for rendering the 3D layer (albeit with some potential inaccuracies), and the NEON unit used to emulate the DS's geometry capabilities.
Legal aspect:
To date I only know of one free emulator that has ever received a cease and desist from a corporation (UltraHLE). Two PS1 emulators have been fought by Sony, but they were commercial - Sony has ignored every free PS1, PS2, and PSP emulator. Likewise, Nintendo has done absolutely nothing about the myriad other N64 emulators, some capable ones released not terribly long after UltraHLE, nor have they said anything to any authors of GBA, DS, or Gamecube emulators. The authors of FirestormZ (a commercial suite of Nintendo emulators) claim that they got a cease and desist from Nintendo after announcing their to be commercially available GBA emulator, but given that they took preorders anyway and didn't release anything for years (which, when they finally did, performed much worse than they said it would) all signs would say that they were lying about everything, including the C&D.
DS emulation may still increase piracy, but I'm certain that it'd appeal to many people who own DS's and own the games they want to play (whether or not they are capable of ripping copies themselves). If there were an adapter to read DS games (via USB perhaps) then this could be deterred further, but I think such an adapter would be a bigger target than the emulator itself.