Really strange.

Do you have any SET RELATION that might be coming into play sporadically?

>Problem still not solved. I not only deleted all the indexes, but the table also.
>
>As for the SMB issues, I've deactivated SMB v2/3 on the (virtual) server, but doing so also prevent the users from accessing the server.
>
>>Not sure if you've solved this already but just in case: I would also suspect index corruption (possibly due to SMB issues). However, just issuing a REINDEX qon't necessarily fix the problem, you should delete all the indexes and recreate them from scratch.