Your particular spams look like the work of one of the worlds most renowned spammers,
Robert Soloway. Somehow, he has programs running through the backbone that records addresses (new and old), a lot of people think. Microsoft has already successfully sued him but I seriously doubt they will ever see a penny, he's said so himself. The best thing to do about these spammers is report them to authorities.