I came across http://www.machinablewax.com while researching various CNC related projects. It's a mixture of Wax and Plastic (polyethelene I think) and is much harder, has a higher melting point and is much more stable than regular wax. It comes in precast blocks, 3D printer filament and in bulk chips which you melt down yourself. If you save the shavings and cut offs, you can melt and reuse them too!!
It can be cut and worked using standard woodworking / metalworking tools or carved by hand. I used a 1/4" spiral up-cut bit to do the milling and it can be found here - http://shrsl.com/?~bc19 . It machines very nicely and it's very easy on tools. There is no visible wear on any of my blades after working this stuff.
Not only does it make an ideal material for prototyping, mold making, jewelry manufacturing, It can also be used in the lost wax casting method. Once it was cut out, I used an old hacksaw blade which was heated with a propane torch to make the slight adjustments for fit and to "weld" the two pieces together.
What makes this stuff so great for prototyping is that if you have an absolute wreck of a project, you can simply remelt the material and try again.
Links—Machinable Wax - http://shrsl.com/?~bc19
Up-Cut Bit - http://shrsl.com/?~bc19
Torch - http://shrsl.com/?~bc19
Knife - http://shrsl.com/?~bc19