I know that your sharing model complexity is compounded. Are there any other pain points?
I've used Territories only once and I'm not sure I'd recommend them ;)
Self-service for users. Key business people in given geography can assign territories at will without involving IT. Combine it with "Delegated Administrator" and you get power users trained to deactivate employee that leaves, transfer all his records to new owners if needed & reassign territories within the sales team.
It's immediately visible on the record that if it sits in several territories - different teams do business with this customer. "Account Teams" might not yield same result and "sharing button blowout page" is not for the faint of heart.
User can be in more than 1 territory - better than Roles. Bigger companies can have teams split in a matrix model. One axis is "geography", the other can be "brand" (product portfolio the team focuses on, maybe "old company" if a merger happened recently or sometimes even "sales channel"). So you'd have Territories for geography and brands in Roles.
Makes record visibility and "security by obscurity" easy if that's what the company really is after. It will be a stupid example but say if http://www.amrest.eu/ uses Salesforce and Territories and offers office catering - they could decide they don't want the Pizza Hut sales team to know which offices are served by KFC. If you have many brands it'll be painful to maintain sharing rules but territories are just data.
You have an option to save the Territory hierarchy of report's creator like it happens with Role hierarchy on Account & Opportunity reports.
Territories are treated as "setup object" and are carried over to dev. sandboxes like Roles, Users etc.
What's not so nice
My former employee wanted to use Territories for both Accounts and Contacts. As far as I know (I wasn't around when the decision was made) the only way to use it with Contacts is to enable Person Accounts which comes with it's own set of headaches ;)
Same as Person Accounts - can't be deactivated.
We had an incident where manually shared hierarchy of territories in one geography was wiped out (data migration team performed an "ETL test run" to production instead of full sandbox and wiped existing data for one of the countries). It was easy to restore Accounts and Contacts. It was impossible to restore sharing info, this data doesn't end up in Recycle Bin. To be fair I suspect it's the same with manually shared records though so you can't really blame Territories for that. Just be very, very careful when you'll hear "our structure is too complicated to fit into criteria-based sharing or even some Excel file to upload; just give us access to production and we'll click through the sharing ourselves".
If I recall correctly we also had to resort to some ugly hacks to store full territory hierarchy on the Territory record. I don't know why we needed it (maybe reporting purposes, maybe something else) but net result was that we had a nice recursive trigger that was writing "US / West Coast / California / Los Angeles / Downtown district" in the "Downtown district" territory's custom field. Of course keep it down to 255 characters if you want it to be searchable in reports, WHERE clauses etc ;)
There was a limit on how many criteria-based territory assignment rules you can have? 30 or so? Colleague wanted to write assignment rules per post code and he run into troubles with that (I don't remember the details though).
Territories are treated as "setup object" - can lead to many frustrating "MIXED_DML_OPERATION" errors in unit tests (like when you want to create a Queue and then a normal object). I think we gave up at some point and kept "unit test hierarchy" and inactive "unit test user for territory 1" records in production, it was so hard to write unit tests that wouldn't rely on existing data. Create User, create a Territory, assign him, create an Account - boom, headshot.
Territory object is royal pain in the a$$ to query for. Similar to Group & Group Member - you have hard time using dots & subqueries to traverse the relationships. To be fair you probably don't have to anymore with introduction of this awesome thing called UserRecordAccess but still.
Just a few points of clarification regarding Territory Management capabilities as it relates to Person Accounts and Contacts:
The Territory Management feature in Salesforce natively supports assignment of Account and Opportunity objects, not Contacts.
While Person Accounts represent an individual, they are a type of Account record, they are not the same as Contacts.
Salesforce Territory Management assignment rules can provide visibility to Account related objects such as Contacts and Cases.
When Person Accounts is enabled in an org the contact sharing organization-wide default is set to "Controlled by Parent" and cannot be modified. Therefore when defining the Contact Access Setting for a territory all options are not supported. This would also be true if you do not have Person Accounts enabled and have set your contact sharing organization-wide default to "Controlled by Parent".
How about the fact that it doesn't work with leads? We've love to implement using this instead of the complex custom object and trigger setup we have, but without it being applicable to leads, it's useless to us. Thankfully someone started a request chain. You can up-vote the idea here: