I bought http://www.ebay.co.uk/itm/301393870750?_trksid=p2057872.m2749.l2649&ssPageName=STRK%3AMEBIDX%3AIT these 4Mb chips and they work as expected.
The 512k ESP-01 use a SOIC memory whereas all the higher density memory is SOIC-W (wider) . However, it is still possible to solder them in place. Remove the old chip - I use a heat gun with a very fine nozzle. Then bend the pins on the replacement chip underneath it. It can then be soldered to the ESP-01. The more modern 1M ESP-01 are laid out to use the wider chip so are even easier to upgrade.
All setting etc. will be lost so you will need to reflash and then connect on 192.168.1.4 to set up again.
All the ESP modules can be upgraded. In the case of the ones with shields over the chips this is a bit trickier but with care the shield can be removed with the heat-gun and then the memory upgraded. The shield can also be replaced using the heat-gun.