Right, as requested, the summary.
A lot of people recommended Soekris, described as being "built like tanks", The Net4801, for example, has CF for booting, 3 x ethernet, and a serial port. http://www.soekris.com . There was some concern about the longevity of their power supplies, however.
Also had multiple pointers to http://yawarra.com.au, who stock soekris and PC Engines WRAP systems.
Some people suggested looking on trademe for linksys WRT54GL's, and putting openwrt or similar on them, although serial ports could be an issue there.
Also put forward was the ALIX series (http://www.pcengines.ch/alix.htm), also available from http://nicegear.co.nz in Christchurch
And then a colleague sent me to opengear.com, who do these little boxes that look like the old milan media converters, which come in a variety of options, with up to 4 x RJ45 serial ports (cisco pinout), multiple ethernets, usb, temperature monitor, dry contact connectors, and even versons with 3G cellular or 802.11 WiFi - http://www.opengear.com. These look like they have quite some potential.
So in no particular order,
soekris���� http://www.soekris.com
yawarra���� http://yawarra.com.au
mini-box��� http://www.mini-box.com.au/purchase/browse-detail.asp?menuId=48&start=1&laCode=ENGAU&productId=174
mini-box �� http://www.mini-box.com.au/purchase/inner-page.asp?laCode=ENGAU&menuId=44&pageId=220
ITX board � http://store.mp3car.com/Fanless_Morex_T1610_Mini_ITX_Case_p/enc-030-w.htm
openrd ���� http://www.globalscaletechnologies.com/t-openrdcdetails.aspx
Atom boards http://www.ascent.co.nz/productspecification.aspx?ItemID=384988
FIT PC��� � http://www.fit-pc2.com
Alix��� ��� http://www.pcengines.ch/alix.htm��� http://www.nicegear.co.nz
opengear��� http://www.opengear.com/product-acm5000-images.html