Country Code Transformations

Python 2, 119 bytes

def f(s,e,c):
 r=max([s[0]+f(p,e,c-{p})for p in c-{s}if s[1:]==p[:2]]+[e]*(s==e)+['!'],key=len)
 return[r,'!']['!'in r]

Try it online!

Takes country codes as a set of strings; returns longest path or ! if no such path exists.

Retina, 108 bytes

+/(?m:^.*\b((..).)(?!.*\1).*\2$)/_L$`\b(..)(.)(?!.*\1\2)(?=.*\1$)
$=$2
mL$`(...),(\w*\1)\w*$
$2
N$^`
$.&
1G`

Try it online! Link includes test suite. Takes input in the order set, terminal, initial. Explanation: Works by generating all possible paths, filtering on those that include the destination, and taking the longest. Explanation:

+

Repeat the command until it does nothing (because there are no more matches).

/(?m:^.*\b((..).)(?!.*\1).*\2$)/_

Operate only on lines whose chain can be extended.

L$`\b(..)(.)(?!.*\1\2)(?=.*\1$)
$=$2

List all of the new possible chains.

mL$`(...),(\w*\1)\w*$
$2

List all of the chains that include the terminal (cut to the length of the terminal).

N$^`
$.&

Sort in ascending order of length, then reverse the list.

1G`

Take the first. In the case of a tie-break, the last to be generated wins; if the set is in lexicographic order then this will be the last in lexicographic order.

Jelly, 29 bytes

ḟŒPŒ!€Ẏ;ṙ-ɗ€Ḋ⁼Ṗ}ɗƝẠ$ƇLÞṪ;Ṫ}¥/

Try it online!

Golfy, but inefficient answer that generates all combinations of all power sets of the country code set minus the start and end, and then checks which ones fit the rules. A dyadic link that takes as its left argument the set of codes and its right argument the end and start in that order. Returns 0 if no path exists. Otherwise returns the longest path, and if there is more than one, the last as determined by the order of the input set.

Jelly, 42 43 bytes

ṭ@Ɱ⁵ḟṖ⁼¥Ƈ0ị$Ḋ$ƲßẎ;W)
ÇẎ0ị$Ḋ⁼⁴Ṗ¤ƲƇLÞṪṭ@;Ṫ}¥/

Try it online!

A full program that takes three arguments: the starting country in a nested list, the final country and the list of country codes. Returns a Jelly string of the longest path if one exists with the sort order determined by the reverse of the listing of the country codes. If no valid path exists, returns 0 followed by the last letter of the destination. Works recursively, and handles longer cases relatively efficiently.