Have you observed that the black spots are more prevalent in or near fine detail such as trees, grass? That's what I observed with the exact same issue I had with Tri-X. In my case, I ran it through an old folder, but was quite careful to make sure it was clean, the rollers were free, in good shape. Looking at the negatives, it looks like the emulsion simply flaked off.
In my case, I used Rodinal to develop, but there's zero percent chance a lab used it unless they hand develop film. Can you inquire what chemistry they use?
What's the lot number on your box of film? Mine's 1021 011, EXP 07/22