Well I am not sure why the '!' was giving you weird information but the single quotes would not have made it done anything good, I would suggest the results were just lucky.
Using your new input data and changing field 2 for 3 I get the correct results for both files irrelevant of order:
Code:
$ awk 'FNR==NR{a[$3$4] = $1;next}a[$3$4] && a[$3$4] != $1' f1 f2
Dc id 168 20
P d 76 0
P f 76 19
V d 75 0
V f 75 19
G f 9 19
G t 9 18
$ awk 'FNR==NR{a[$3$4] = $1;next}a[$3$4] && a[$3$4] != $1' f2 f1
Di i 168 20
Mm d 75 0
Mm f 75 19
Mv d 76 0
Mv f 76 19
n f 9 19
n t 9 18
I hand checked all results and they are correct.
Good luck with the python solution.