Usually 2000mAh is the best bet, i think it's the lowest safe current(?). Corrections?
The "mAh" rating only applies to batteries, as it indicates how much current (mA) can be delivered over a given time (h). For mains powered devices, the rating is simply stated in millamps (mA) or amps (A).
Anyway, you're on the right track with the 2000 figure. The power pack needs to be rated at 2000mA (2A) or more. From memory, the official GP2X power pack is rated at 3A.
Doremi's unit is only rated at 800mA, so it's not powerful enough. (And just a note on multi-voltage power packs in general; they will only deliver their max rated current at the lowest voltage setting. The current capacity goes down as you select higher voltages.)