After inspecting more of my messages, I've noticed that the From addresses that don't get recognized correctly have the email address enclosed in < & >.
For example, the following address works correctly:
Buy.com -
Buy.com@enews.buy.com
But the following address does not:
Buy.com Deals<buy.com_offers@enews.buy.com>
It appears that < and/or > messes up the regex search.