I've also got this error in the past for a different reason which the -r switch cannot fix. What happened is that I based files to add to the zip with the following bash code/variable
somevar=`ls -1 somedir`
The problem is that ls just lists the files off as if it were in the current directory and this is why zip is complaining (essentially the files do not exist to zip because it is being told to look in the wrong/current directory).
If this is your issue you can correct it like so:
somevar=`ls -1d somedir/*`
As you can see I used the -d switch and also /* at the end of the directory name and then the files were successfully added.
zip -P password /Volumes/Storage\ 4/archive -p /Volumes/GGZ/faster/mybigfolder/*