Does the perfect circle of light you get without the negative holder shine directly perpendicularly down on your baseboard? If not, it's pretty certain to be alignment trouble. I had pretty much all the same problems you're describing with my Omega DII, and I thought it might be the bulb, the condensers, lens coverage, all the things you're looking at, but eventually it was the off-center circle of illumination that clued me in. Everything else was fine.
DIIs are fairly simple machines, and I imagine your enlarger isn't too different. To figure out how to realign it took me an almost complete tear-down (actually, I had to tear-down my entire darkroom to get at the enlarger first even), the whole project accomplished with a screwdriver, a set of hex-wrenches and a torpedo level, in maybe four or five hours. But I was starting from scratch without too much native mechanical aptitude- now that I know how it works it'd probably only take me 10-15 minutes. Essentially, the lamp-house has to sit nicely on the negative-stage, and the negative-stage must be parallel to the lens-board and the base-board.
Very worthwhile project, though. Omegas are notorious for going out of alignment, so even if this isn't the problem at hand you ought to check it out. All parts of my prints look better since, not just the corner I don't have to burn in anymore.