Looking at the photo here: http://www.flickr.com/photos/hoeken/3316849629/sizes/l/ the finest part seems to be the CPU in the middle. The footprint details are here: http://www.siongboon.com/projects/2005-09-07_home_pcb_fabrication/footprint/TQFP-44%2010x10x1%20G4012-001.pdf.
0.56mm pads with 0.24mm gaps, that is certainly achievable with milling. Here are examples of bits fine enough, no idea how much they cost. http://www.lpkf.com/products/rapid-pcb-prototyping/tools/surface-tools.htm You would also need a high speed spindle with good bearings. Someday I will get round to trying it with HydraRaptor as it certainly has the resolution.
I don't know what power laser you would need. I know Zach told me the laser printer they use for Acrylic, probably 25W-40W, will not etch PCBs.
I would also like to try spark eroding it with a fine tungsten electrode.
The chemical etch method starts to look more attractive after seeing this; http://www.instructables.com/id/Sponge-Ferric-Chloride-Method-Etch-Circuit-Bo/
One problem you have with all these methods is making the vias. If they are big enough you can just drill a hole and solder a piece of wire each side, but there are some on that board underneath the surface mount chips, so they would need to be perfectly flush. They could probably be moved.
The commercial milling machines cover the board with a plastic sheet, drill holes in it where the vias are, insert a paste type substance with a squeegee and then bake it in an oven to form conductive plugs.
Sorry I can't be more authoritative on this until I have tried some of these things myself. The only PCBs I have made in the past where done with a laser printer onto plastic film, then UV exposed onto photosensitve PCB material and etched with ferric chloride in a heated bubble chamber. It was about 15 years ago and I never did any surface mount stuff, only 0.1" pitch though hole.