Why is the shortcut to "select previous tab" not reliable in Safari?
I've never experienced this in Safari, and I expect there is some sort of conflicting shortcut. Either that, or "quite frequently" your mouse focus is in Flash or Java, and shortcuts aren't being sent to the browser (which doesn't seem terribly likely given the frequency).

Due to having switched to Safari after several years in a row of using Chrome and Firefox, I've set the Previous/Next Tab commands to ⌥+⌘+←/→, using System Preferences. Again, I've never had any issues with switching, so I'd suggest (if you're willing, and can't find the source of the problem) to set it to another shortcut you can remember.