I know, it puts you in a pickle. Most cryptocurrencies use public blockchains where transaction data can be verified by anyone. It's an invasion of your privacy, but you could show records proving you deposited those coins to an address/addresses connected with that Decoin exchange. Your receiving address on Decoin would, of course, have to be connected to a known Decoin address by some service like WalletExplorer, Breadcrumbs, or similar.