That said, is it technically and otherwise possible that I request Alice to sign a message that would prove that her wallet address sent funds to Bob's wallet?
Yes, but only if the bitcoins weren't sent from a shared wallet like MtGox. If they were sent using a wallet like Bitcoin-Qt where you control every private keys for your addresses, Alice might be able to sign a message using an address that was used in an input to the transaction with Bob. I say "might" because in Bitcoin-Qt the addresses used as inputs to the transaction might all be hidden because they were change addresses.So, it is possible to say for sure that Alice paid Bob, but the inability to sign a message to that effect does not indicate that you aren't speaking with Alice.
