We first start by generating all 5! permutations of the 5 letters:

letters = Take[Alphabet[], 5];
perms = Permutations[letters];

And now we create a relation graph, the vertices of which indicate if two permutations share no common letters in the same position as each other:

relationTest = FreeQ[#1 - #2, 0] &;
graph = RelationGraph[relationTest, perms];

We now find all cliques of the graphs with exactly 5 vertices, these correspond to the valid 5x5 letter matrices

pass = FindClique[graph, {5}, All] ;

And now we require that in each letter matrix, each person is a given a new 5-letter string. So we create another relation graph among the letter matrices, where the vertices indicate whether the two matrices give new strings to each person. This took about 1 min on my laptop:

cliquesAreDistinct = FreeQ[Total /@ Abs[#1 - #2], 0] &;
cliqueGraph = RelationGraph[cliquesAreDistinct, pass];

And find the maximal clique, which has 24 5x5 combinations satisfying the constraints

best = FindClique[cliqueGraph][[1]] // Sort;
best//Length
(*24*)

Here they are

a   b c   d e
b   a d   e c
c   d e   a b
d   e b   c a
e   c a   b d


a   b c   e d
b   a d   c e
c   d e   b a
d   e b   a c
e   c a   d b


a   b d   c e
b   a e   d c
c   d a   e b
d   e c   b a
e   c b   a d


a   b d   e c
b   a e   c d
c   d a   b e
d   e c   a b
e   c b   d a


a   b e   c d
b   c a   d e
c   e d   a b
d   a b   e c
e   d c   b a


a   b e   d c
b   c a   e d
c   e d   b a
d   a b   c e
e   d c   a b


a   c b   d e
b   d c   e a
c   a e   b d
d   e a   c b
e   b d   a c


a   c b   e d
b   d c   a e
c   a e   d b
d   e a   b c
e   b d   c a


a   c d   b e
b   d a   e c
c   e b   a d
d   a e   c b
e   b c   d a


a   c d   e b
b   d a   c e
c   e b   d a
d   a e   b c
e   b c   a d


a   c e   b d
b   e a   d c
c   d b   a e
d   b c   e a
e   a d   c b


a   c e   d b
b   e a   c d
c   d b   e a
d   b c   a e
e   a d   b c


a   d b   c e
b   c d   e a
c   e a   b d
d   b e   a c
e   a c   d b


a   d b   e c
b   c d   a e
c   e a   d b
d   b e   c a
e   a c   b d


a   d c   b e
b   e d   a c
c   b e   d a
d   c a   e b
e   a b   c d


a   d c   e b
b   e d   c a
c   b e   a d
d   c a   b e
e   a b   d c


a   d e   b c
b   e c   d a
c   a b   e d
d   b a   c e
e   c d   a b


a   d e   c b
b   e c   a d
c   a b   d e
d   b a   e c
e   c d   b a


a   e b   c d
b   c e   d a
c   b d   a e
d   a c   e b
e   d a   b c


a   e b   d c
b   c e   a d
c   b d   e a
d   a c   b e
e   d a   c b


a   e c   b d
b   d e   c a
c   a d   e b
d   c b   a e
e   b a   d c


a   e c   d b
b   d e   a c
c   a d   b e
d   c b   e a
e   b a   c d


a   e d   b c
b   a c   e d
c   b a   d e
d   c e   a b
e   d b   c a


a   e d   c b
b   a c   d e
c   b a   e d
d   c e   b a
e   d b   a c

Formatting should look better now.