exchange 2013 sendas permission randomly denied

okay Experts --- brainstorming needed.
Migration from EX2007 - EX2013 CU3
all good.
Customer previously had address book segregation using ADSI edit and deny permissions for Address Lists. This have all been reset.
Upgraded CU3 - CU5 - all good
Upgraded CU5 - CU6 to fix problem with slow lookup for address books.
After that, this error appeared:
The customer have 100+ shared folders. SendAs permissions is given to a domain local group. Members of that domain  local group is a global group - in that group the users needing SendAs permissions are members.
When working with Outlook in Online mode - they randomly cannot send an email as the shared mailbox. They can send 5 messages, then the sixth message is denied - given the error message "you don't have permission to send as the shared mailbox" - then either close and reopen Outlook and send, or just wait a couple of mins - then it works.
this happens at no predefined time intervals. it happens to all shared mailboxes, regardless of amount of emails, and connections. it happens in both online and cache mode.
We upgraded to CU7 - due to this https://support.microsoft.com/en-us/kb/3009291 - but still no fix.
the customer have 1 root domain (naturally) and 2 subdomains, with exchange in one, and the other no exchange recipients.

We set throttlingpolices to unlimited - still no fix.

Then one fix - if we give the user permission directly - it works. if we use groups only, it doesn't work. But it worked from CU3 via CU5 but stopped working in CU6 ---
Microsoft Support says ---- eeeh ... we don't know -- upgrade to CU8 - but that's no solution, as customer have several 3rd party integrations not compatible with CU8

soooooo ---- anyone?