I would recommend sandals. Teva Cross-Tera specifically. The only times sandals don't work is for desert, due to prevalance of thorn bushes, and for wet snow and slush conditions. If you anticipate snow and wet slush, I would suggest supplementing the sandals with some neoprene booties or socks, either worn alone or worn with the sandals.
For merely cool weather, you can add some home-made cordura socks. This is what I will be using on my future trips to replace the neoprene socks I used in the past. pattern is here. Takes about 3 hours to cut and sew, working at my usual plodding pace, less for a skilled sewer. These cordura socks will also provide mosquito and tick protection. If you plan to wear them constantly for that purpose, then bring along some spares, at 5oz/pair.
Sandals with hook and look closures (such as Teva Cross-Teras) will collect crud in the grasslands, but this is mostly just an annoyance. The hook-and-loop will almost certainly not wear out in 30 days or 600 miles.
If used carefully, Teva Cross-Teras will easily last 600 miles of rugged hiking. Scree slopes and talus are not particularly hard on the soles of shoes, by the way. In particular, they probably abrade the soles LESS than ordinary concrete sidewalks in the city, because the abrasion is spread on different parts of the sole rather than concentrated. The big risk in the mountains is scraping the sides of shoes against certain types of very abrasive rock. With sandals, the sides means the straps. The straps on Teva Cross-Teras is very heavy nylon--far more durable than the nylon of most fabric boots. By contrast, the straps on Chacos is flimsy polypropolene--I sliced through those straps due to a single careless misstep and then had to throw the sandals away because I couldn't repair them on the road. I have walked in the Pyrenees, Corsica and other mountains in Europe extensively with sandals, on very rough scree slopes, and see no reason why durability would be a concern, assuming you use Teva Cross-Teras and not some other brand.
I strongly advise bringing along a 1oz tube of either Shoe-Goo or McNett SeamGrip in case the bottom sole and upper sole separate and need to be glued back together. This can happen to any shoe or boot, even a brand-new shoe or boot, due to manufacturing glitches. It takes a day for these glues to cure, but losing a day (which is unlikely in any case) is better than having the whole trip ruined because your footwear falls apart. I have only used Shoe-Goo myself for repairing shoes, but I have used SeamGrip for other purposes and feel quite confident about its holding strength.
Sandals give poor footing when they are wet and you are making steep descents, because the foot tends to slide towards the front of the sandals and the straps don't hold the foot very securely. But such steep descents with wet feet are the exception, and this one disadvantage of sandals is compensated for by a host of advantages. In particular, you don't need to worry about getting wet. Just plow right on through streams and bogs.
Here are some more suggestions regarding sandals, from the clothing writeup at my website:
- Avoid leather sandals, since these will rot in outdoor conditions (other than the desert).
- Avoid sandals with quick-release fasteners, since these can break. The Cross-Teras use hook-and-loop, which is much more reliable, though it tends to pick up crud outdoors (especially in grasslands). Sturdy ladder-locks are probably the best fasteners, but only if the straps are of heavy nylon. If the straps are thin nylon or polypropolene, they can easily abrade outdoors.
- Avoid sandals which don't have some sort of anti-microbial treatment in the topsole. If sandals nevertheless start to smell, soak them in a strong solution of bleach (sodium hypochlorite) for a few minutes, then rinse, then coat with baking soda (bicarbonate of soda) to get rid of the bleach smell. A similar treatment will remove stink from the feet (but don't let the feet soak for very long!).
- Avoid sandals (like Chacos) which try to support the arch or otherwise fix supposed imperfections in the design of the human foot.
- Avoid sandals (such as Chacos and certain models of Tevas) which use other than sturdy nylon straps. Thin polypropolene straps can be easily cut by rubbing against sharp rocks in the mountains.
- Avoid sandals whose straps are merely glued between the top and bottom soles, since these can pull out when subjected to strong forces, such as walking downhill when the sandals are wet. Some Teva models and lots of cheap model sandals are constructed this way. Chacos and Teva Cross-Teras (at least the older Cross-Teras, I'm not sure about the latest versions since I've not yet torn them apart to check) run the straps all the way from one side to the other, between the top and bottom soles, and thus the straps cannot pull out regardless of the force applied.
- Avoid sandals with flimsy bottom soles which will wear down quickly under use.
- Avoid sandals whose bottom soles lack traction for wet slippery surfaces. Most river sandals are specifically constructed to have excellent traction on wet slippery surfaces, like river rocks, so this isn't usually a problem with river sandals.
- Avoid sandals with neoprene padding on the straps, since this lacks a anti-microbial treatment and hence tends to stink after a while. The Cross-Teras have such neoprene padding on the heel strap. I removed this and then resewed the velcro back on without the neoprene padding.
- Avoid sandals which don't allow the toes (especially the small toe) to spread out properly.
- Be wary of sandals which have enclosed toes or ridges along the sides which prevent rocks from being easily shaken out. I say be wary rather than avoid, since this may or may not be a problem, depending on other factors. Keen brand sandals have enclosed toes. I haven't yet used Keen sandals.
- Avoid sandals with seams or connectors which sit directly on top of tendons, such as the tendons on top of the foot, as this can cause inflamation of the tendon.
- Flip-flops are the simplest of all footwear, and almost never cause blisters or other problems to someone with strong feet. The big negative is that they can easily fall off and then be lost, such as while fording a river. They are also usually flimsy in construction, though Chaco makes some flip-flops with a durable sole. All in all, I can't recommend them for hiking. However, if your regular footwear ever falls apart on the road and you must buy replacements, carefully considering buying flip-flops at the same time and carrying these for a few days. This way, if the replacement shoes start causing problems in the middle of the wilderness, you can use a combination of barefoot and flip-flops to get back to civilization.
Now to answer some of your questions regrding Teva Cross-Teras:
(a) How many miles are you getting out of them? At least 1500. I don't know for sure since I replace my sandals whenever I can, just to be on the safe side, even if the sandals are still in good condition.
(b) What kind of miles you are hiking (on/off trail, type of terrain - rocky, brushy, etc.)? Typically I spent 6 months hiking each season, of which 4 months is lowlands (forest, low mountains, asphalt, city streets) and 2 months is high mountains (tundra, scree slopes, forests).
(c) Where on the shoe are they failing? Slowly but surely, the sole wears down at the front of the foot. Eventually, I imagine the sole would wear through to where the strap runs between the top and bottom soles and at that point the strap would be cut, thus ruining the shoes. I have never reached this point yet. Note that the bottom sole can and sometimes does separate from the topsole. I prepare for that by having ShoeGoo available.
(d) How do you know they've failed if the failure is not obvious? Failure of Tevas is soft-failure--slow and obvious. With Chacos, I experienced hard failure--a single misstep and I sliced through the straps, thus rendering the sandals worthless. I had to hike barefoot to the nearest town to get replacements.