I am pretty much sure I solved it by clearing the fast search cache in Adobe Reader.
My explanation why this problem occurs:
Even without encryption, the fast find feature from Adobe Reader is using the /ID entry (if it is set) to somehow identify all text content of the document.
Once I have cleared the fast find cache from "Preferences -> Search" I was again able to search
So in future I will use something similar to md5(#timestamp#) to make sure every document has its own unique fileIdentifer stored in /ID entry of the document trailer.
Thank you for your hints
Regards, Ole