Pretty much any CO2 laser on the market will be able to cut the mylar stencils you require, even the 40w models. If that's all you're doing, I don't think you really have a big worry on power. That said, I imagine that once you have a laser, you'll quickly find more to do with it than simply cutting stencils! -- I'd say that the anywhere up to 60w would be fine for what y'all need. CO2 lasers have a minimum level that they'll actually fire at, and thus, the higher the wattage, the higher the power of the minimum setting. Cutting thin mylar paste stencils like you intend to, you want to have the flexibility to get your laser power dialed right where you need it, to get the finest accuracy for small pitch components.
Nice-to-have would be a motorized Z axis to help you get your focus dialed in just right to minimize the kerf.
Most machines in your price range would be rigged for air assist, which although not entirely necessary for your application, is nice to have. If nothing else, it helps keep the lens clean by keeping cutting smoke from fouling it.
As for precision, I believe that pretty much any machine on the market from a reputable manufacturer would be able to give you consistent and repeatable results at that resolution. I've seen people with el-cheapo ebay K40 machines which, after some minimal fiddling, can reliably cut stencils for .5mm components. Given that the K40 (from ebay anyway) is pretty much the Yugo of chinese laser machines, I think you'll find you have good luck with pretty much anything from Redsail or G.Weike.
One thing that'll eat into your budget as well will be customs brokerage, import duties, and shipping to where you are. I'm not familiar with shipping from China, and ports of entry for the east coast/great lakes (if your machine is big enough to need to be shipped by ocean freight) but you may need to arrange shipping from the port of entry to your location.
Did you have your eye on any particular model from G.Weike?
Cheers!
-C