Beau - I came across this solution. Basically, when used with the Email Services it will forward the Email Service email to another legit email address with an actual inbox.

So, temporarily set this code up with the Email Service in question.

Then set up the long Email Service address as a forwarding address to whatever address you want customers to send emails to. Now when Gmail (or whoever) sends the forwarding verification notice to the Email Service address the email will get bounced to some other legit address. Then you can read the email and get the verification code and then finish setting up the long email as the forwarding address. 

Then once it's set up you can turn this class off. Problem solved.

global class email_Handler implements Messaging.InboundEmailHandler {

        global Messaging.InboundEmailResult handleInboundEmail(Messaging.InboundEmail email, Messaging.InboundEnvelope envelope) {

            Messaging.InboundEmailResult result = new Messaging.InboundEmailresult();
            String attachment_body;

            //Reroute Verification Email
            if(email.plainTextBody.contains('We have received the following request to add this')){
                sendVerificationEmail(email, 'xxxxx');
                return result;
            }
        }

        private void sendVerificationEmail(Messaging.InboundEmail email, String toAddress){

            Messaging.reserveSingleEmailCapacity(1);
            Messaging.SingleEmailMessage mail = new Messaging.SingleEmailMessage();
            String[] toAddresses = new String[] {toAddress};


            mail.setToAddresses(toAddresses);
            mail.setSenderDisplayName('Test');

            mail.setSubject('Test');
            mail.setPlainTextBody(email.plainTextBody);
            mail.setHtmlBody(email.htmlBody);
            Messaging.sendEmail(new Messaging.SingleEmailMessage[] { mail });

        }

    }