A chave de junção deve ser classificada de forma lexical.
Portanto, use um shell com suporte para substituição de processos (ksh93, zsh, bash) e:
join -1 3 -2 1 <(sort -k 3,3 1) <(sort -k 1,1 2)
Ou com um shell POSIX / Bourne:
sort -k 3,3 1 | {
sort -k 1,1 2 | join -1 3 -2 1 /dev/fd/3 -; } 3<&0
Isso ajuda a entender como o join funciona. join lê os arquivos concorrentemente linha por linha e compara as chaves de junção, se eles forem iguais teremos uma correspondência e produziremos o resultado, se key1 < key2, continue lendo file1 até que key1 seja igual a key2 (ou maior, em cujo caso começamos a ler o arquivo2 e assim por diante).
Isso explica por que não funcionará se os arquivos não forem classificados por chave.
Note que este é o caso de todo join mas como uma extensão, GNU join não reclama enquanto as chaves coincidirem. Ele falharia como todos os outros, na primeira incompatibilidade se as linhas não forem ordenadas por chave.