2つのListに共通する要素を抽出する

こんなのどうでしょう？

var targetList = Enumerable.Range(0, 350000)
    .Select(i => Guid.NewGuid())
    .ToList();


var searchList = new HashSet<Guid>();
searchList.Add(targetList.Skip(100).First());
searchList.Add(targetList.Skip(101).First());

//最近はこれ
//var searchList = targetList
//    .Skip(100)
//    .Take(2)
//    .ToHashSet();

var resultList = targetList
    .Where(g => searchList.Contains(g))
    .ToList();

searchList.AsParallel().Intersect(targetList.AsParallel()).ToList();はどうでしょう？

順序要件を見逃していたので。
targetList.AsParallel().Intersect(searchList.AsParallel()).ToList();

何というか振りかえると、Whereでよかったんじゃないかとか、即時にリスト化しなきゃならないのかとか、考えるべきことは色々あるように思います。

searchListのvalueをキーにした連想配列を用意してしまえば、targetListのリストの数だけ回せばいいので、searchList+targetList回だけ回せば済みます。