Are you sure it's stock? Post the RPM in fifth gear at a certain speed and we can check that the transmission didn't get swapped with a lower geared one at some point.
Only reason not to clean the EGR is if you don't think you'll be able to put it back together correctly.
Your short trips certainly aren't helping, but you should be able to get at least in the 30s in all but the worst conditions.