What happens to step down converter effiency when current consumption is very low
In active mode the current consumption of the ICs are around 20 mA and
  according to the datasheet the efficiency of MAX640 is around 90 %.
  Hence the total current consumption will be around (20 mA/ 90 %) =
  22-23 mA, right?


No, that doesn't make any sense. 

Look at the graphs in the data sheet typically this one: -



With a load current of 20 mA (not the chip current consumption) the efficiency is around 90% for the MAX640 so, if the output voltage is 3.3 volts, then the output power at 20 mA is 66 mW and the input power to the device and load is 66 mW/0.9 = 73 mW. So, if the input voltage is 9 volts and a power power of 73 mW is taken, the current is 8.11 mA.


  But most of the time I want to shutdown ICs (and MCU) to get a
  consumption of maybe 10 uA.. looking at the datasheet (EFFICIENCY vs
  OUTPUT CURRENT) it is not even plotted... what will happen? Can I not
  use the MAX640 if I drop the current consumption that low?


No, it won't be plotted because there is no need - the device is in standby mode and the load is not powered. In standby, the device takes 10 uA typically and the load is not powered.



However, if your load took only 50 μA, there would still be a significant power consumption just to keep the MAX640 operating in non-standby mode. At 50 μA load current (see the graph above) the efficiency is 50% hence input power will be 2 x 3.3 volts x 50 μA = 330 μW or, from 9 volts, the overall load and device current would be 37 μA.