Incoming Mail Processing when contact does not exist?

We have incoming mail processing turned on to allow automated case creation when an email comes into our help account. This works great except when the contacts email does not exist in our system. What is the best way to handle these? It would be awesome if the system created the account based on domain and then still proceeded with case creation. We are currently having to monitor the inbox, create the contact and then create the case when this occurs. It also seems the case will not auto create after the fact once contact is in the system. Looking for ideas on how to make incoming mail more efficient for us. Thanks!