The trouble is that we don't really have the whole story here. Is the client saying that he/she flew on a particular flight and the airline has responded (in truth) that they have no such record (from the pax list) of that? In which case it is understandable that they place the burden of proof on the client.