MacroMigrationService has a few issues:

In order to find out which pages to migrate, it creates the following search:

new ContentSearch(getAllLegacyMacrosQuery(), null, null, filter)

This ends up calling the following constructor (after a few calls to super and this):

    public AbstractSearch(SearchQuery query, SearchSort sort, SearchFilter searchFilter, ResultFilter resultFilter) {
        this(query, sort, searchFilter, 0, SearchConstants.DEFAULT_LIMIT, resultFilter);
    }

Where SearchConstants.DEFAULT_LIMIT is 10 (obviously).

So only the first ten pages found are actually checked for migration.

If we set this limit to Integer.MAX_VALUE in the debugger, we hit the next problem:

    @Deprecated
    public SearcherWithTokenAction(Query query, Filter filter, Sort sort, int startOffset, int limit, Set<String> requestedFields, LuceneResultFilter luceneResultFilter)
    {
        this.query = query;
        this.filter = filter;
        this.sort = sort;
        this.startOffset = Math.min(startOffset, SearchConstants.MAX_START_OFFSET);
        this.limit = Math.min(limit, SearchConstants.MAX_LIMIT);
        this.requestedFields = requestedFields;
        this.luceneResultFilter = luceneResultFilter;
    }

Where SearchConstants.MAX_LIMIT is 500.

This would not be a problem if the client of the above search would be pagination-aware, but behold! - it isn't. It just happily copies the first 10 resp. 500 search results into a SearchResultsBatchWorkSource (which in, itself, is completely unaware of pagination that is forced upon it by SearchConstants.MAX_LIMIT).
This might just be triggered by the fact that searchResults.getAll() does NOT (as the name would suggest), return all search results, but only the ones that are on the first page (i.e. max 500). Bummer.