The "rare" batteries are not really a problem, because they are rechargable, and come cheap from DX with free shipping.
The ones the big 200mW laser uses have a big capacity, and should last for a while even with the powerfull pump diode inside..
CNI lasers (Nova, LG..) are regulated. And very well at that! I just tested one of their drivers, and it is amazing! The power of the laser will not be better with higher voltage batteries. The power will always be the max possible (depending on heat), as long as the batteries are above a certain minimum voltage.
I use 1000mAh AAA Ni-MHs in my >150mW CNI, and it works great. I have two pairs, so i recharge one, while using the other.
Lithiums might keep it in regulation a bit longer, but as soon as they would be half empty, the power would start droping, rendering them useless. It's just too expensive. Whenever possible, go with rechargables. Cheap DX lasers do not have regulation, and there the power really does depend on the battery voltage.