I made this slightly modified advanced random example file to showcase how Voronoi and Cellular break if you move around (maybe others too, but less visibly).
Just use the arrows to move around and very soon you'll see it breaking in straight lines like in the example below:
Is this a bug?
EDIT: it looks a lot like a bug, so I reported it, still, any insights are welcome.