Right, but since all this data is available, they can trace it (remember, in your scenario, that they also have internal ids for transactions and tie them to users, and that is how it is resolvable). Surely they should charge a retrieval fee and return the money.
You are assuming the BTC are still in the account of the person who "owned" the address. And the internal ID would just show that a deposit came into the said address and that the proper user account was credited with the BTC. None of that will have any of your information in it.