Advanced Search with Proximity criteria does not export right number of contacts

When using Advanced Search with proximity criteria, the output of the search shows the right number of contacts. However, when we then go to take an action on those contacts (selecting the All records radio button), the number of contacts it performs the action on is far fewer than what is shown. Here are steps using our system (and attached are screenshots):
1. Go to Advanced Search
2. Choose the "Address Fields" criteria and put a Zip code, then 50 miles for the "Find contacts within" section
3. Optionally select a Contact Type (Individual in the screenshot examples)
4. Run the search and see that you have X number of contacts - in our case, 6120 records total
5. Select the "All 6120 records" radio button and choose "Add Contacts to Group" selection in the action dropdown and click Go
6. See the next screen showing that only Y number of contacts are going to be added (in our case, 115 of the 6120 total)

You can also choose "Export Contacts" instead of add to group, and the resulting export file will also have less than the total number of contacts.

Note: If we use the Custom Search -> Proximity Search tool instead of Advanced Search, all records that show up in the results also show up for exporting or putting to a group. This seems specific to Advanced Search with proximity criteria in our case.