At that sort of gain level you have to start being really careful about power supply rejection, particularly at higher frequencies - I once built a circuit that could be cranked up to a gain of 10,000 at up to a couple of MHz, and figured out that I needed to to put RLC filters on each power pin, so that the current drawn by the output stage wouldn't feed back ripple onto the power rails that could leak through into the output of the input stage.
My calculated supply filters worked fine, and the final circuit was stable for every gain up to 10,000, though the outpty was a bit noisy at high gains - I did have to make one modification to the printed circuit, but that was to deal with the unspecified input capacitance of the Texas Instruments TLC2201, which was high enough to call for a compensating capacitor in parallel with the feedback resistor.
You've also got to be a bit careful with the layout - a little bit of capacitative or inductive coupling between input and output can be fatal, but an inch or so of physical separation is plenty if the relevant tracks run over more or less solid ground plane.
---------- Bill Sloman, Nijmegen