I seem to remember that my SIII was finicky. You mentioned releasing the power button while keeping the home and volume up pressed. I recall having to do the exact same thing. From a powered off state, press all the buttons you mentioned, but release the power button after a second or two. Once I got the hang of it I was able to do it easily.
And like cozzbp is saying, there are apps that offer boot options without using any hardware keys.