So I recently replayed through the game, after finding out that it's actually possible to get both the painting and rubaiyat before sinking. (I thought if you had the rubaiyat the painting would automatically be missing)

Anyway I had dialog in this order:
- Overheard Zeitel tell Sasha that he couldn't find the painting and there's a traitor (presumably Willie)
- Took the car keys and went to the hold and found the painting
- When I talked to the crewman there he says he witnessed a German guy minutes before looking for a painting

Why couldn't Zeitel find it? You find it in the original crate as on the manifest AFTER Zeitel presumably went to the hold.