Do each private key corresponds to one and only one mnemonic phrase? and do each mnemonic phrase decode to the exact same private key always?
Mnemonic seeds are first converted to the master private key (seed) before being generated to a private key. Each private key can be generated from one and only one master private key since HMAC-SHA512 is applied to the master private before being generated and unless a collision is found, the hash will not be the same.
Mnemonic phrase will always decode to the same master private key and subsequently the same private key.
Does all permutations of the words calculates to a valid private key? If not, does wallet software try multiple times to generate a valid phrase?
Yes, according to BIP39 standards. You can select the words from the wordlist yourself and you can generate a seed from using any mnemorics. However, depending on your client, you might need to have the correct checksum.