I actually have just watched your first video and I think the biggest problem is that the AI simply does nothing when they don't see you so you don't even need Skin graft, you can wait multiple turn for your CD to come back while they probably should move and look for you.
So if they can't see you they'd probably go for the next visible threat but if they don't see anyone (only one person sneaking or everyone is sneaking or there is a mass invisibility) they should skill move to either find the sneaky enemies (even if they can't detect invisibility they should try).
Now the challenge is to feel the AI is searching and is not cheating and always sees you.
To me in the video the sneaking mechanics is what breaks the AI more so than Graft skin makes you too strong.
