Error while relocating (“filename.nef” couldn’t be moved to “20” because either the former doesn't exist, or the folder containing the latter doesn't exist.)

Where are the originals now stored, and where are you trying to relocate them to?

and this only happens with some (around 20 pictures of 20k in my library)

Is there anything special about these files? special characters in the filename? Do they display correctly in Preview, if you use "File > Reveal in Finder"?

Can you relocate them to your System drive, e.g. the Desptop?

I am still not sure about from where to where you are trying to relocate:

When I search for the filename, and finds one of the files that are problematic and I try to consolidate the original it says selection does not contain referenced files.

This suggests, that your library is currently managed - otherwise the library would have referenced files.

But if "locate referenced files" is working, your library is probably already a referenced library, so what is it? Referenced or managed? And are the originals or your library on an external drive or on your system drive?

That random files cannot be moved, suggests a problem with incompatible file systems. Are all your drives formatted for Mac? MacOS Extended (Journaled). If either the source drive with your library or the destination drive has a different filesystem, you can get exactly such errors with filenames and pathnames, when copying. Collisions between filenames can occur, when one of your drive has a case sensitive formatting and other drives not.

, my internal drive is encrypted, the external not.

That is probably causing the error. It would explain, why Aperture cannot access the folders with the images it wants to relocate.

Rather than encrypting your external drive as well, I would exclude the Aperture library from the encrypted part on your system drive.

That would still not explain why this happens only to a small percentage of my files, also the external drive is not encrypted so there should be no problem moving the files that are there (?).

We have seen a similar problem about two years ago. Aperture lost continually the connection to some original image files because of the encryption of the home folder. It was random, which files were affected by the problem, because it was a question of timing - a kind of race hazard. If the part of the library with the image in question already had been decrypted, all was well, but if the folders along the path to image were still encrypted, the access would fail.

Error while relocating (“filename.nef” couldn’t be moved to “20” because either the former doesn't exist, or the folder containing the latter doesn't exist.)

This error message could be referring to the folders inside your Aperture library, not to the destination folder on your external drive.