In the end, the issue was trivial.
I used base::sort() to create the levels of a factor. (To ensure that they would always align, even if the data was in a different order)
The problem is, that the default sort method depends on the locale of your system. And R CMD check uses a different locale than my interactive session.
The issue resided in this:
R interactively used:LC_COLLATE=en_US.UTF-8;
R CMD check used: LC_COLLATE=C;
In the details of base::sort this is mentioned:
Except for method ‘"radix"’, the sort order for character vectors
will depend on the collating sequence of the locale in use:
see ‘Comparison’. The sort order for factors is the order of their
levels (which is particularly appropriate for ordered factors).
I now resolved the issue by specifying the radix sort method.
Now, all works fine.