One important step in figuring out where the problem lies is to try making some prints using a glass-sandwich negative carrier, if you're not already doing so.
I did some printing over the weekend with my LPL 4500II - modest enlargements (4.5 x 6.75") from 35mm Tri-X negatives. As it happens, I did precisely this test - made some prints using both the LPL glassless 35mm carrier and also the glass carrier. Regardless of how careful I thought I was being with the glassless carrier, the prints from the glass carrier were distinctly sharper and cleaner looking, even to the naked eye.
I suspect that it was a combination of the negative being flatter and also not flexing unpredictably under the on-and-off heat from the enlarger lamp and the varying intervals between when I focused and made the printing exposure.