Mail servers have become very strict. They try to vaildate every email they recieve. When CFWebstore sends the Merchant validation email after an order, it uses the customers email address as the FROM address. Technically this SPAM since the store is impersonating the customers email address while sending email. Some email servers are either blocking or greylisting these emails because they don't have the proper validation (username/password).
The solution is to change the FROM address in the merchant email to a validated email address. We will use the Merchant email address found in Admin > Site Design > Main Settings.
Via FTP, go to shopping/checkout/post_processing/act_mailorder.cfm ~line 96.
This will work with all versions of CFWebstore 5.x or 6.x.