Without access to D&D spells like zone of truth I would see if I could search the cabins of all the people, if the people refuse, they could be hiding something, if they don't have anything to hide, then why not let me in to look, which, as has been mentioned earlier could have lots of plot threads open, or, as another option, once the ship reaches port it could be possible to contact local authorities to try and find it, assuming that they're not corrupt, or at least help the people from being upset with you for searching unreasonably.
GM
EDIT: The logic seems sound, the only other problem would be if no one had access to the cabin between the two events, aside from the crew, then it would eliminate a lot of options, while if someone would have had to enter unnoticed, like at a party where everyone else is, then that excuse has a lot more validity, as he would not have been able to sneak into the room unnoticed then, but he could have gone in sometime else