Label-disjoint paths in directed graphs
The problem becomes NP-complete ... this is a "graphical" :-) reduction from 3-SAT ... it should be self-explanatory (... if not let me know).



Two notes:


+X1a, -X1a, +X1b, -X1b,...,+X2a,-X2a, ...,dum1,...,dum4 are all distinct labels;
in the figure  each label appears $\leq 2$ times; but it is straightforward to make each label appears exactly 2 times adding some dum nodes+edges+labels to pair them up.