It has to be set on all. But it also has to be set on the n8n server and all n8n workers to exactly the same random string. After all is that the string that got used to encrypt the credentials, and they can only be decrypted with exactly the same string again.
The error message is saying that N8N_ENCRYPTION_KEY is currently probably set to different values on n8n servers and n8n workers. For that reason is n8n unable to decrypt the credentials.
That is strange, So the key is always the same and the issue only occurs when you restart the main n8n instance?
Is it on restarts or updates, My first thought is maybe the environment variable isn’t set correctly so it is using the value in the config file and the storage volume is not persistent so it is being replaced on each update.
I have just given this a test using the compose file you provided and after adding a credential and restarting the main process or the worker process the error didn’t occur. I then restarted the entire stack and everything still continued to work.
When you restart the container how are you doing it and which container are you restarting to trigger the problem?
As a test you could try running a workflow that has a function node that only contains the below that would show you what encryption key is being used.