The message can only be decrypted with the key the vendor sent it to. Since you deleted your private key you threw away the key to unlock that message. You may have created a new key but the vendor didn't send the message to your new key he sent it to your old one.