Thanks guys for your answers, it gave ideas to look at this issue again, ideas and motivation!
A good idea was asking which side striker I was using: I was using a passenger side striker and could not adjust it enough; I switched to a driver side striker and now the door is held shut pretty tight. I have also added washers in a few spots under hinge bolts to straighten the door a bit, it also helped.
Now, I think I cannot hear the door rattle anymore, which is pretty cool. But I can hear other noises better, which will also need fixing some time...
And Bartamos, about Alberta, when it is not covered in snow, it is pretty dry and yes, pretty dusty. And then, go and drive on a dirt road with a door that does not seal...
