Not all overclocks are guaranteed. I have a 7850 and am happy with it running at 1 ghz. It will go farther, but this is for everyday use. I would be happy you got as far as you did. I'm not sure newegg will RMA it if nothing is wrong with it.
I've been approved for a full refund rma but have yet to decide if i should bother. With that being said I have no idea what happens once a RMA for a gpu is received, for all I know they simply test to see if it works and if it does they ship it back to you or they just ship it to HIS.