I know you said lasers are not ideal, but since you can do this with a hand scribing tool, I imagine it's possible. Is it possible to get a vector file to play with? Something that would support a 0.005-0.07 spot size? Those are the lasers I have, but a fiber laser would be 1/10th that size, and can mark metal, so that seems like it has even more potential.
If you can get the laser to produce a reflective surface within the groove it should work. The ideal tool is something conical with a very tiny radius at the tip, something like 0.002" so that there's a nice concave and self-polished surface within there. There are two sample/example G-codes generated from Holocraft that you could try. They are identical in terms of the hologram they produce but one uses strictly G1 feed commands while the other utilizes arc-feeds instead (someone was curious about the difference so I created these to show them).
Here's the links to the G-code produced:
Let me know if an SVG of the groove optics would be better than G-code for you to test out. I'd love to see what kind of results you can manage w/ a laser :)