Very badly. In fact all my normal (woodworking) tools went blunt without much progress. Eventually we settled on doing it like this: use a very thin saw to mark out the stations every 2 cm or so for depth + 1 mm, then use a belt sander (graciously borrowed to us by the father of a friend) to take it down to the marks, then endless hand sanding until it was good. It looked absolutely gorgeous when it was done. I don't remember what kind of wood it was though, the amount of dust was staggering. On one day I accidentally left the door to my attic bedroom open and everything inside was covered in dust. That beltsander did a great job though, and I don't think we'd have pulled that off without it.

If I had to do this today I'd use a metalworking mill. There is no point in trying to work wood that hard with regular wood tools, they just won't keep an edge.