And here is a much cleaner solution using ParticleRandom.
It’s fixed to 2x2 uv’s in my test but should be no problem adjusting to larger ones. Notice the division with 1.99 instead of 2.0, I seemed to get flicker on some particles when using 2.0 (possibly due to 1.0 mapping to an invalid subuv, but not sure).