I see from your email that you're involved with U.S. Africa Command, eh? Interesting. I'd like to hear what you do for that branch. Or is that the right word? Branch? Department? You tell me.
So…shoes. You wear them down on the outside? You're an over-supinator. When your feet strike the ground they tend to roll to the outside, rather than the more normal pronation motion to the inside. Nothing necessarily bad about over-supinating, and it's probably a function of your flattish feet.
What you need is a durable stability shoe that can take the weight and mileage. I've always thought Asics were some of the most stable shoes on the market. A good shoe for you might be the Asics Gel-Trail Sensor 4 ($110). It's a rugged trail shoe designed to handle stability issues. And for rocky trails it has a trail-specific outsole and a protection plate to guard your soles.
New Balance is another maker renowned for tough, stable shoe. The New Balance MT910 ($110) is a classic design that works extremely well. It's built tough for a big guy on rough trails, and has a midsole/shoe design that is meant to keep your foot as stable as possible.
You might add an after-market insole to your shoes, such as the low-volume Superfeet Black Premium Insoles ($35). I think you'll find that they add some comfort and stability.
Also, don't be shy about cycling through shoes fairly rapidly. You are putting a ton of stress on shoes. Even if they look okay after three months, toss 'em. The midsoles will be broken down by then.
Hope this helps!