Intuitive explanation on why stochastic encoding performs better in channel coding
Well, I think you are conflating two things. It is correct that in a lot of settings probabilistic encoding (e.g., Polar Codes, Convolutional Codes, LDPC Codes) [assuming you know a good model for the noise process of the channel] does much better than algebraic coding, intuitively because channels have memory and block codes ignore that memory.
However, Ahlswede's Identification Problem is quite different. It is NOT a traditional channel coding problem There is a good review  here
The author states

In the problem of identification via channels, introduced by Ahlswede and Dueck the receiver is only
interested in testing whether a particular message was sent, but the encoder does not know which message
the decoder wants. Errors are now considered in terms of false alarm and missed identification. It turns out
that for this case, one can design systems such that the number of different messages one can identify grows
doubly exponentially with the blocklength. The trick is that each message can map into a list of codewords
and the encoder selects one randomly. As long as the fraction of the pairwise overlap of these lists is small,
the error probabilities will be small