Q: Executing a script with ./script.sh fails while "sh script.sh" works I'm very befuddled by this error and don't even know what to google for:
Failure -  Executing a script with:
./test.sh 
bash: ./test.sh: "Permission denied" 

Works - while these apporeaches work:
sh ./test.sh
Works
bash ./test.sh
Works

The test script:
cat test.sh 
#!/bin/bash

echo "Works"

With all execute rights:
chmod 777 test.sh

ls -als test.sh 
4 -rwxrwxrwx 1 edo edo 27 13. Feb 10:41 test.sh

I'm quite clueless to why this is happening as it doesn't make any sense to me and I have no clue what words to Google for to properly describe the behavior..

A: Executing a script by depending on the shebang line works quite differently from passing it as the argument to a shell.
In the former case, the file must reside on an executable partition, and must contain a valid shebang line to an existing shell.
In the latter case, none of that is necessary, as the shell you're calling the script with takes responsibility for these things.
NOTE that you're not using the same shell for these tests either: the first infers bash, while the second uses sh.
My guess is that the partition your script resides on does not allow execution; mount -v will tell you if this is the case.
