I've had countless puzzles fall in the dirt when I used them outside, and it made them slow for the rest of their life. One thing that has worked sometimes is washing all the pieces individually. There's plenty of methods to doing that, but what I usually do is put them in a bowl filled with soapy water. I bet it will work well on yours, since you don't need to worry about messing the stickers up.
Best of luck.