The work I'm guessing you refer to on colliding prime factors is by Heninger et al., "Mining Your Ps and Qs", USENIX Security 2012 [1]. That paper does not mention anything about PRIMEINC causing this problem. The cases they found all related to bad entropy or extremely bad ways of generating moduli (like, pick two random values from a short list of known primes and use that as the modulus---an IBM product actually did this).
In fact, PRIMEINC is provably secure for generating RSA keys (though this was only shown somewhat recently): Abboud and Prest [2] analyze the distribution of outputs from PRIMEINC and show (see Section 4.1) that the security loss is negligible under quite mild conditions. Concretely, generating a reasonably sized RSA key using PRIMEINC rather than uniformly random primes reduces the security of RSA by a few bits at most.
But in some sense this reinforces your point---it was definitely not trivial to show that a tweak as seemingly simple as PRIMEINC is actually safe!
I remembered reading https://rjlipton.wpcomstaging.com/2012/03/01/do-gaps-between... which I suppose only says this _could_ be very bad.
Very interesting and great that it was resolved in the negative!
An example from a few years ago: To find a random prime, the "correct" way is to generate a random number, and check if it's prime. However, for performance, people would instead generate a single random number, n, and then try n+1, n+2, etc. until they got a prime.
The result? Too many RSA keys used the same primes, because primes following "a long run of non primes" were much more likely to get picked than say the upper prime in a prime pair.
Once two RSA keys share a prime, you can use Euclid's algorithm to find out which. Get a large batch of badly generated RSA key pairs, and you were likely to find some collisions.
In conclusion it's not that looking for performance optimizations is inherently bad, but you really have to strictly prove that you don't change anything important.