When we migrate starting in September, we will migrate 8000 to 10000 users and we are planning on having one MBM.PUF file on one fileshare.
As we migrated 2000 users before, there was little to no impact in performance on the desktop while parsing that file, but how does this work with 8000 to 10000 entries in the PUF file?

The Priasoft ProfileManager utility uses file-locks to ensure that concurrent access to data is not an issue.  
The ProfieManager opens a handle to the file and steps thru the file, one line at a time making comparisons between the information on that line and the current mailbox entry in the Outlook profile it is analyzing.  As soon as a match is found, the file handle is released.
In this design, the application will only have the file open for as long as it take to find the related mailbox.  in the worst case scenario, the entire file is scanned only to find no match.
However, since only one line of the file is read at a time, this keeps memory/RAM demands extremely low (each line is around 500-600 bytes) on client machines, in contrast to downloading the entire file to memory before searching.
There should be no concerns with 8000+ users and the ability of the ProfileMangaer to do its work.