are the store email addresses valid addresses for your domain.
for example, if your domain is www,mydomain.com, the store email addresses need to be valid addresses from that domain:
sales@mydomain.com
if the emails are still not coming through, you should contact the host to see if they can look into the smtp server error logs to see why the emails are not being relayed.