When machining wax I have found the harder the wax the better.
Cutter type doesn't matter much as long as it is sharp and turns faxt, like in a dremel tool. I would use a cutter with as few flutes or cutting surfaces as possible (coarse cutter) in order to make sure there is room for the cuttings and not remelt the was. Too, I suggest using a vacuum whiile cutting to keep the swarf (cuttings) from caking up on your releif or engraved paths.
-Mark