Mapping Center Answer:

The first issue (graphical infringement) is caused by the Standard Label engine only comparing the text, and not the background or effects; so the marker from the highway shield and the halo on the text are not accounted for in our collision detection functionality.  

You can address this in the Standard Label Engine's Properties on the Conflict Detection tab, by Setting the Buffer to something between 50 and 100.

That said, it's not going to produce a perfect solution given the second issue you describe.  Remove duplicates works a little differently in the Standard Label Engine--it is applied at the the "feature" level, which means for line labels that we assume that conterminous line features with the same name constitute the same feature.  So the Remove duplicates will apply within a feature, but for double-lined interstates, each direction is a different feature. 

While there are higher order solutions like creating annotation, or tagging only the features you want labeled in your data, both are a daunting task given the scope of work I imagine you have.  I use an imperfect hack when faced with this problem, which is to filter some of the features you might be labeling out.  It looks better, but runs the chance of not labeling something.  

In the case of Frontage Roads, I modified the Label Class SQL Query to:  "TYPE" = 'FR' AND MOD("OBJECTID", 5) = 0

Where I added the MOD function against the Object ID, which basically says randomly select some of the features.  You could vary the mod number.  For your data (I still have it) 5 worked better than 2 or 3.

Sorry--there's no perfect solution.