First, I would check with your SMTP provider, it appears you're using Mandrill. This way you can see exactly why it was set to "Not Valid" in the first place. You can do so by logging into Mandrill, going to Settings > Rejection Blacklist and searching for the email address. This will tell you whether they marked you as spam or it was a soft or hard bounce.
Second, you can mark a email as "Valid" at any time simply by resaving the email in AllProWebTools. You can resave it by clicking on the email address in the CRM record and clicking the green check box to save it.