I believe the issue is a limitation on the query capabilites built into the action. The following is a quote from the documentation.
Please note that filtering related to these fields: To, Cc, To Or Cc, From, Importance, Fetch Only With Attachments, Subject Filter, is performed using first 250 items in a given mail folder. To avoid that limitation you can use 'Search Query' field.
I think you'll need to create and use the Search Query field instead of the built in fields.