Why the signature of the same message changes in some wallets, but not all?
You're seeing the effect of RFC6979.

When generating a signature, some randomness is needed (called the nonce), as there are multiple valid signatures for the same message/key pair. The algorithm used, ECDSA, is extraordinarily vulnerable to weak randomness. An attacker who knows just a slight bit of information about your nonces can learn your private key after observing many signatures.

However, someone figured out that it doesn't need to actually be random. The only thing required is that it is unpredictable for the attacker. As a result, a standard was created that suggested using basically the hash of your private key and the message as your nonce. That standard is called RFC6979, and Bitcoin Core switched to using it in version 0.10.0. Clones that forked off before that version typically don't use it.

I have no idea why pubkey recovery does not work without deterministic signatures. I think it should work fine.