Eric, you were right after all! It was the hosting company. Sorry Beau if I had you scratching your head over this. As I have never actually had a form send email, I never ran into this problem. Here are the tips for anyone hosted through Hostmonster (which may be similar to using another hosting company, just call tech support to get specifics for your situation) and who have email hosted ELSEWHERE, ie: GAFYD, NOT through the hosting company. Further, we have our domains hosted elsewhere too, so the actual DNS file isn't at your hosting company.
STEP 1 - Change email routing setting to Remote.
1. Log in to cPanel.
2. Go to Domain section, select DNS Zone Editor.
3. Select the domain in question.
4. Go to "MX (Mail Exchange)" section and select the "More..." link just underneath the heading after "Email Routing."
5. Choose "Remote Mail Exchanger" setting, then the "Change" button.
STEP 2 - Create a dummy email account.
1. From cPanel, go to "Mail" section and choose "Email Accounts."
2. Use the form to create the same email account you use for the contact form on your WordPress install. Settings you choose don't matter and email will not be sent to this dummy acount. It just authenticates the specific email address to the host so they don't block those emails from being sent.
STEP 3 - Have a margarita while testing your new form. It works! Woohoo!
1. Do you need instructions for that?
Hope this helps some others having this same problem. Cheers!