And if the Tor user pays the fee from non-P2PKH addresses (e.g., segwit P2SH addresses or multisig P2SH addresses), the Tor user can't sign the message using those addresses.
Sure they can. They can sign from the private key(s) used to sign the transaction. The public key associated with the private key(s) used to sign a transaction is public information once the transaction is broadcast.