Пффф, след десет опита най-после разбрах къде е проблемът. Когато търсиш думите в третата част, итерираш първо по думите, а трябва да е по намерените букви, тъй като може думата на определена буква да е по-назад в третата част, а явно думите трябва да се вадят по реда на буквите, мачнати от първата част. Така че foreach-a долу го направих така:

for (int i = 1; i < firstWord.Length - 1; i++)
            {
                char letter = firstWord[i];
                int length = result[letter];

                foreach (string word in thirdPart)
                {
                    if (word.Length == length + 1 && word[0] == letter)
                    {
                        Console.WriteLine(word);
                    }
                }
            }

Мерси че ми показа как да си оптимизирам Regex-a, но грешката просто няма откриване наистина... 

Мерси много за отделеното време!!!