Unfortunately, the 'new' number you have received isn't actually new at all. It will have come from a pool of numbers allocated to VM. As numbers fall into and out of use, they move from/to the pool. Numbers will return to the pool if a customer leaves VM and doesn't take the number with them.
Numbers in the pool may also have been used by businesses in the past and/or may have had a history of nuisance calls which may have resulted in them being changed and returned to the pool of numbers.
The nuisance calls which we all receive are largely generated automatically by overseas scammers. Their equipment dials blocks of numbers in turn trying to make connections. Unfortunately, no numbers are safe from this automated process. The caller IDs which are used for these scam calls are typically faked so trying to block individual nuisance numbers is of no use.
The only way to deal with them, and still retain normal use of your landline, is with a call screening device such as trueCall or with a phone which has screening features built into it. These devices filter the calls. They screen out the scam calls and reject them whilst only allowing legitimate callers through and then causing your phone to ring.