I was thinking of some kind of PICAXE chip
Use an P89C51RD2. 3 x 8 bits available straight away, two sacrificed to the serial port, 22 bits
Yep, that would do it. Here's the datasheet. It will give you a one chip solution but you'll need a PIC programmer to go with it and need to find a suitable compiler to generate the code. Watch the output currents too. The maximums are 15mA per output, 26mA per port and 71mA for the whole chip. If you're not familiar with PICs you'll find the PicAxe much easier to get to grips with as it (in conjunction with the programming software) looks after most of the 'tricky bits' for you.
You don't need ANY programmer, you bang it directly through the RS232 port, so its dead easy - Force the PSEN line high at reset and you're in "programming" mode. NXP supply a free package to program it called FlashMagic. For what the OP wants, Keil do a "free" compiler which will have enough memory for what they need to do. Failing that, there is SDCC and a couple of free Pascal compilers, as well as Jan Waclawek's wonderful BASIC52 replacement at http://efton.sk/basic/index.htm - put this in the 89C51 and all the programming can be done at a terminal, and the code runs very well. I used to use BASIC52 in production instruments, with sideorders of assembler for speed in a couple of places.
i'll have a look at this chip.
by the way, apparently on the new X2 PicAxe chips you can configure which pins are input or output, so if like me you need a lot more outputs than inputs you can just set it that way, but ive had a look and cant see how its done.
On a classic 8052 ALL the IO pins are inputs and outputs - there is no configuration required.
If you have need for a bank of higher output digital I/O (up to 50mA/ch) you can always interface to the loads using a PS2501 or similar. They're isolators but can be used in isolated or non-isolated mode.
The largest PicAxe - the 40X2 - will only give you 16 outputs (if I'm counting correctly). Look at P74 HERE. If you're planning to use a PicAxe, I'd be tempted to use a pair of the new 20X2 chips. The first would do the RS232 bit and drive 8 of the outputs directly. The second would be programmed as an adressable latch and would handle the other 11 outputs, the inputs being generated from the first chip. Don't forget the max current from a pin is 20mA and the max from a chip is 100mA (figures from memory - check!) so buffering may be necessary.Alternatively, use a 20X2 and 3 octal latched buffer chips (e.g. 74LS373) which would make the addressing easier and increase the current drive.
Whoops - Miscount in method 1. Not enough pins.
I'd go for one 20X2 and 2 x 373 chips. Drive three of your OPs from the PicAxe directly (with simple buffer if necessary) and latch the other 16.
What sort of speed are you looking to switch the outputs at?