What about the unpoppable bubble wrap that comes with shapeways products?
It's difficult to pop that bubble wrap... But it isn't unpoppable
(Source: I've done it
Foam rubber is pretty good, stable and light. Check out the PAW
packaging for what I am talking about. You can get foam in various densities and can cut it to accommodate even odd shaped puzzles.
I recommend this as well, as stated, it can be cut to the shape of said object being transported. And don't get too soft or too hard of foam, as it can be a downfall later.