There are several possibilities:
1. Send an email directly to your Email to Case Premium routing address to determine if the problem resides with forwarding on your company's mail server or whether the problem is in your Salesforce.com / Email to Case Premium configuration.
To obtain your Email to Case Premium routing address, navigate to Setup | Build | Develop | Email Services and choose Email to Case Premium. Your Email to Case Premium routing address(es) will be listed at the bottom of the Email Service page. If sending an email directly to the routing address successfully creates / updates a case in Salesforce, than the issue is likely related to forwarding on your mail server from your support address(es) to the Email to Case Premium routing address.
2. Ensure that you cleared both "Accept Email From" boxes when adding the email service during initial setup. Navigate to Setup | Build | Develop | Email Services and choose Email to Case Premium. Check both the Email Service and the Email Address(es) under that email service, and remove any values in the "Accept Email From" boxes. Additionally, you should verify that both the Email Service and Email Address are set to "Active". See the sample screenshots below.
3. Check that the "Context User" specified in the Email Address (under the Email Service) is an active Salesforce user with either the System Administrator profile or the required permissions.
4. Check that the "Context User" is assigned a license to Email to Case Premium. If you are using a trial license, or your organization has purchased a site license, this step is not applicable to you.
5. If none of the above steps resolve the problem, review the following knowledge article for additional information, or contact Internet Creations support by sending an email to email@example.com.