I've used a router to carve grooves into foot-pad foam before. It works fine on flat surfaces that can support the body of the router. I haven't worked out a good way to get it to carve out raised edges around the heel and under the arch of my feet yet. Anyone got a way to do this?
Be careful with the router - they spin fast and can easily cut you up!