How possible is it to set write permissions on storage folder on symlinked install?
Symlinks don't really have permissions themselves. 

If I had to hazard a guess, it sounds like your deployment script isn't setting the correct permissions on the craft/storage directory, maybe because they're being recreated every time you deploy? 

I think you have a couple options:


set the permissions on that directory correctly (see the above link) after you deploy
change your deployment strategy a bit.


If it were me, I'd tell the build/deploy script to ignore the craft/storage directory altogether. Setup your own storage folder that won't be touched by your deploy script (say above the releases folder) after you deploy. Then just tell Craft to use that location.

What is the symlink actually pointing to? 

You could really deploy anywhere on the server too, not just in the typical nginx web root. (I prefer not to even touch the default distro locations because any update could modify your web files.)

If you want to go down the path of permissions, it gets a little murkier. I don't have a ton of experience with something like Capistrano (or whatever deployment system you're using) but your deploy user needs to have sudo permission to be able to change the permissions so your PHP user—likely the same user as the nginx user but not the same as the deploy user—can write to it.

One way around this is PHP-FPM. Setup a new fpm pool with the user/group of the deploy user then add whatever user you're running nginx as to that user's group (eg usermod -a -G deploy-user www-data)

That will let nginx read files from the deploy user but let FPM write to the folder because it owns it. Then you won't have to worry as much about after-deployment permissions.

It's also cheap jail if you set it up properly.

(If you're running Apache as mod_php with nginx in front of it, it'd be a similar setup.)