There's a really simple way to do this with Linq. Basically, you concatenate the lists together and group them, then you search for items where the count of them is 1. Try this query out for size:
List<int> countDistinct = firstList.Concat(secondList)
.GroupBy(x => x)
.Where(g => g.Count() == 1)
.Select(g => g.Key).ToList();
It's as easy as that - and reads a lot easier to read than trying to compare two independent loops.
I did a comparison between this solution and the solution presented as Solution 3, and the time difference was quite staggering. I created two lists, the first had 1 million numbers in it, and the second had 2 million numbers - only 6 numbers don't match between the 2 lists. The Contains solution is a very inefficient search mechanism on large sets, so the search ends up taking an inordinate amount of time. To be honest, I gave up waiting for the second search to return after about 20 minutes. The Linq solution took 1745 milliseconds.