You will need a 300mw laser at least - anything less than that and you are fighting with the noise floor.
This sounds like it would be true only if you are measuring the brightness of the reflected dot in order to calculate distance. From the link I posted above, using a cheap webcamera and a consumer grade laser, calculating distance using angular measurement requires much less in terms of laser power.
This homebrew system uses a scanning mirror and photodetector for angular measure, and again, a cheap laser pointer:
http://letsmakerobots.com/node/2651
So - in theory - you could scan a laser (or better, project a laser "line" with a diffraction grating or cylindrical lens), and use a web camera or other system to take distance measurements based on the displacement (and angular measure) of the dot or line; without the need for a larger laser.
I do understand the need of a larger laser for aesthetic and performance (by the artist/musician) reasons; it looks better, and it allows the artist a measure of feedback as to where their hands need to be positioned. A larger laser would probably even make the measurements more accurate (but not necessarily; I know that industrial laser distance rangefinder scanners use sub-5mw lasers, and they are highly accurate). However, for a prototype device, I don't think it is strictly necessary.
Then again, I've never built such a device; I am just basing my conjecture on what others have built and my knowledge of how such devices work.
