You send them the bitcoin to an address they give you.
How do they give you the address? If they send it via SMS or email, then you have some proof that it came from them. If they print it out on a piece of paper, perhaps with a QR code, and hand it to you, then they can easily deny that it belongs to them.
Could they deny getting the bitcoins when I go to the outlet to collect the cash?
Sure, but you can prove the bitcoin are in the address you were given using blockchain evidence. The harder part is proving that the address belongs to them.
Could the address be traced back to them if want to complain at the governing body?
Unlikely based solely on blockchain evidence, unless they were careless and combined the coins in the address you have sent to with coins in other addresses which are known to belong to them.
Note that there is not really anything inherently different to buying in the shop - even if you do it all in person they can just as easily say "That address isn't ours". They only way around this is to receive some kind of proof from them that the address belongs to them before you send coins to it. If they do hand over addresses on a piece of paper, then perhaps you could take a photo or video of it being handed over? At the end of the day, if you are going to be sending first (which you always will be with a merchant such as this), then it comes down to trust.