Hello all. Turns out we had a permissions issue on the filesystem for avatars, meaning Xenforo wasn't allowed to create new avatar directories. And it likes grouping users in those directories. So users uploading an avatar could indeed be denied for no valid reason whatsoever...
Though it wasn't due to use stopping new users from uploading avatars, those were most likely to run into the issue indeed (since it happened to users uploading an avatar for the first time, basically).
Should now be fixed.