One interesting angle I've heard proposed with regard to this is that even post-"heat death", there is no guarantee that local pockets of low entropy will not exist. Indeed - quite the opposite is true: let's say being in a maximum-entropy state requires all particles to assume a fully random distribution (otherwise a potential gradient would exist somewhere, a form of order, and the entropy would not be maximized). Now, take a description of an NxNxN chunk of universal "stuff" (energy, matter, etc). Similar to how we can find every string of digits in Pi if we look long enough (each given substring is equal to the search string with probability 1/10^N, N is length of string), we should be able to find every possible chunk in the maximum-entropy universe, with the probability for any given chunk matching being 1/M^N^3, (M is the universal "base", how many options a given location has for what it can be in the encoding we are using).
Long story short, assuming an infinite universe post-"heat death", we'd expect to be able to find every possible arrangement of particles represented at some location, even very complex ones such as the entire universal state we observe today.
Long story short, assuming an infinite universe post-"heat death", we'd expect to be able to find every possible arrangement of particles represented at some location, even very complex ones such as the entire universal state we observe today.