Why do so many logic ICs have output high voltages specified at 3V and 4.5V when they're primarily used at 3.3 and 5V?
I think your assumption of why 3V and 4.5V were chosen (common supply voltages less 10%) is probably correct.  

But your statement that "making sure the load regulation won't effect logic levels is my job" might not resonate with everyone depending on how conservative they are.  If the datasheet did specify min Voh only at 3.3V, then how would you know exactly what the min Voh is at Vdd = 3.0 or 3.1V?  It would probably be OK to assume the same drop, but how sure are you? You could check on some parts that the Vdd-Voh is the same at 3V, but you can't be sure how well it will hold up over process and temperature variations. You can just use a value of 2.9V, and you are guaranteed that it will be OK.

A more useful spec that I've seen on some parts is Voh relative to Vdd, stratified by Vdd ranges, but it's a bit more work for the manufacturer to characterize and test.