Over the past couple years, several companies have switched to biodegradable packing peanuts made from cornstarch derivatives. I don't know what else must be in them, but we found Old Girl happily snacking away on a few yesterday. Cornstarch itself doesn't seem like something that would be particularly scented or tasty, but dogs sure seem to like the peanuts. Perhaps that's a secret tactic for degrading them?
(p.s. her digestion has been completely untroubled by them; after all, this is a dog who loves cat poop...)