What you really need is to find someone who has one of these:

http://www.rolanddga.com/products/printcut/colorcamm/pc-12/default.asp

It's basically a one-off sticker maker, complete with precision cutting.

Maybe http://www.mindspring.com/~agi/ColorCamm.htm?

I can't speak for the people I just mentioned; they just showed up in a Google search, but I've seen the Roland device in action, and it's really nice.

Alex