After doing numerous tests and doing an Outbound Routing debug it was clear that the route wasn't being skipped and it wasn't being marked down. The catch all route was being tried first even though the order of the routes in the Voice Usage had it at the bottom.
Interestingly, if I simplified the regular expression of the route that matched a range of specific numbers to just be one of those numbers, it magically started to work correctly. As soon as I modified it back to the larger range, it would fail.
Knowing that I have done this many times before, I was convinced somehow I hit some sort of bug. So a case with Microsoft was opened. After some lengthy testing, the Microsoft support engineer was just as baffled as I was and was coming to the same conclusion I did.
As a work around, until the Microsoft engineer decided how to proceed, we created two different Voice Usages. The first one was for ranges of numbers and the second usage contained the catch all route all by itself. The routing worked as expected, but this was not ideal, because this would increase the number of Voice Usages across the hundreds of sites in this deployment. I was aiming for the simplest dial plan possible since it was already complex.
Anyway, after a few days the Microsoft engineer got back to us and dropped a huge bomb.
Believe it or not, this was working as designed. He informed me that there was a change in Lync Server 2013 in how it processes routes in a Voice Usage. Lync Server 2013 now chooses the least complex regular expression before it processes the other routes. The reason for this change I don't agree with, but apparently there were some customers that had really large dial plans, where processing a large list of routes in a Voice Usage was taking too long and this change was decided to speed up processing the list.
So... if you have similarly complex in the same usage, the order of the routes matters. But if you mix complex and simple rules in the same Voice Usage, then the more simple rules will always be followed first.
I hate this because now everyone else is forced to create more Voice Usages, sometimes with a single route in them, to have the routing work as desired. The other item that bugs me is that there is next to no documentation of this change and this was not communicated to the technical community in any other way that I'm aware of. This is a big change for a product that a lot of people depend on to be consistent.
I think a better alternative would have been to give the engineer an option to process the routes within a Voice Usage using the Lync Server 2010 method or to switch to the new Lync Server 2013 method. I can see merits to both methods, but ideally I would like a choice.
Now... If you are like I am, you want to know what exactly constitutes a simple rule vs complex rule. Unfortunately I can't tell you exactly. All I can share with you is a somewhat vague answer that I got back.
The algorithm has quite a bit of complexity – in simple terms, the route that has simpler “prefix” will be preferred over more complex ones. The “prefix” is a combination of characters, character escapes, alterations and substitutions (as defined in regular expressions).So if anyone has more detail on this algorithm, I'd like to have it. But in the mean time it doesn't really matter because the permanent fix is to have similarly complex rules in the same Voice Usage and then make sure you test to verify the route order is being followed as desired.