Does VMProtectDecryptStringA/W generate a new encrypted string each time?

As in using it on the same string, and running vmprotect again on an untouched binary, will the encrypted string be different than last protection?

Yes, it will be different.