Apologies if I'm missing something, but I don't see how that solves the problem at all.

Whether or not Alice signs a message before making the transaction is irrelevant. Before the payment is made and the scam has taken place, then there is nothing to be gained by Alice signing a message saying she is intending to make the payment. After she has made the payment, the payment will be verified by a third party viewing the transaction, not by any signed message. And as you point out, with or without a signed message, Bob can still deny the receiving address is his.

Privacy coin or not, hidden addresses or not, without a signed message from the recipient confirming their payment address, there is always the possibility that they deny the address is theirs.