I think this is pretty good evidence that low quality parts & workmanship can get you by for everything except wheels! When wheels fail on tour, you're pretty much stuck. I'd guess that your original wheels had off-brand spokes and weren't tensioned.
It depends on what you want to do with your mtn bikes -- if you think you might tour on them again, then you have to get quality wheels. If they're just for day rides and around town, then keep them trued up and they'll be fine. In fact, I'd say just keep these wheels as a second pair for that kind of riding.
Double walled (= in general, more rugged) and eyelets (= stronger spoke bed) are good to have. Even more important, as said above, are good spokes (use DT, Wheelsmith, or Sapim only). Even MORE important is the build quality (properly tensioned, stress relieved, trued).
Choice of hub is another issue, but doesn't generally affect build quality. (Actually, flange width, amount of dish, etc., do come into play but if you stick to Deore/LX/XT quality, you'll be OK.)
Choosing between hand-built and machine-built really comes down to cost. I avoid that decision by building my own
It's not hard, just requires a few hours and patience. If you get machine-built, have a wheelbuilder check the tension (or do it yourself), and re-true it after a few rides. Most machine-built wheels I see have straight-gauge spokes; as radical
said above, double-butted help make a bomb-proof wheel. In all, hand-built (by shop or by yourself) gives you a better wheel.
So, if you're gonna ride your bikes on loaded tours, get quality wheels. If they're just town bikes now, keep the wheels trued and ride.