After a couple hours with the laser cutter at fablab (many thanks Digiteo!), I have cut a new set of parts for Wall-E's body.

As before, the head is made of plywood slices, glued together. I added a set of holes, so that wood sticks (toothpicks) help keep the slices aligned. 

The 'eyes' part is screwed onto the 'back head' part, so that both parts can be disassembled.