Lars suggested using "high intensity lasers!" in one of his first emails when we started planning for Ice Art 2006. I laughed off the idea at first, but I'm taking it more seriously as time goes by.
Visible light lasers are certainly out of the question; they'd pass right through the ice without heating it. Infrared lasers, on the other hand, have a great deal of potential for ice cutting. Ice has a couple of peak absorption wavelengths at about 1500 and 2000 nm, but it looks like any laser in the infrared band would be worth trying.
I'm guessing that I need at least a 1W unit to do any meaningful experimentation, but the devices I've found so far are quite expensive. If anyone has lead on a cheap IR laser or laser diode (or salvage ideas), I'd appreciate it.