Obviously, Rob don't understand how cryptonotes work.
He mentions Yobit and CCEX, but they don't have cryptonotes in there.
Maybe he treats the Bitcedi wallet like it is like any other bitcoin-clone wallet, but it is not.
If the the block explorer says that there is no Payment ID, then, he missed to put the Payment ID in the right field in the wallet (the last field on the "send" tab).
And by the way... What it means "they've asked me about the payment id and have sent them already"?
You don't send your Payment ID, you include it in the transaction.