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.

The number of permutations of {a,b,c,d,e} is 120. So, there is a theoretical max for the number of combinations (because you want uniqueness of the permutations for a particular person across all combinations). Can we achieve that theoretical maximum. It seems to me that if we start with some list of all permutations, rotate that list by an appropriate amount for each person, then each combination will be unique.

To demonstrate, I'll use three letters to save space:

perms = Permutations[Take[Alphabet[], 3]]
(* {{"a", "b", "c"}, {"a", "c", "b"}, {"b", "a", "c"}, {"b", "c", "a"}, {"c", "a", "b"}, {"c", "b", "a"}} *)

TableForm[
  Map[StringJoin, NestList[RotateRight, perms, 4], {-2}], 
  TableDirections -> Row, 
  TableHeadings -> {{"Person 1", "Person 2", "Person 3", "Person 4", "Person 5"}, {"Combinations", "\[VerticalEllipsis]"}}]

Now, I'm not totally sure I understood your constraints. Maybe you meant that no permutation should show up more than once anywhere. Or maybe your comment about "order of letters" being unique means something different than what I thought. If so, please clarify your constraints, and maybe provide a sample output for a smaller set of permutations.