Finding the Deadlock

Python - 586 539 524 501 485 bytes - 8 = 477

Indentation levels:

1: 1 space
2: 1 tab
3: 1 tab + 1 space
4: 2 tabs

--

import sys
V=set()
t=[[[]]]
for r in sys.stdin:
 r=r.strip()
 if'---'==r:t.append([[]])
 else:v=r[1:];V.add(v);l=t[-1][-1];t[-1].append(l+[v]if'+'==r[0]else filter(lambda x:x!=v,l))
s=lambda l:s(l[1:])+map(lambda x:(l[0],x),l[1:])if 1<len(l)else[]
E=reduce(set.union,map(lambda x:set(sum(map(s,x),[])),t),set())
for v in V:
 k=set();q=[v]
 while 0<len(q):
    u=q.pop(0)
    if u in k:continue
    k.add(u)
    for x,y in E:
     if u==x:
        if y in k:print':(';sys.exit()
        else:q.append(y)
print':)'

Python 2 - 227

Basically makes sure there are no loops of 'precedence'. For example in the second test, the first thread has a a(b) precedence and the second thread has a b(a) precedence.

I was thinking about rewriting this in Pyth as I think it would work well with all the itertools operations, but converting the regex will take some work so for now I'll post this and maybe try to convert it and post another answer later.

from itertools import*
import re
f=lambda t:any(re.search(r"(.)((.)\3)+\1",''.join(p))for i in product(*[[m.group(1)+m.group(2)for m in re.finditer(r"(\w).*(\w).*\2.*\1",e,16)]for e in t.split('---')])for p in permutations(i))