You can't replace the static method through replace-with, but you can make the static methods call GWT.create on a class that has one implementation, and use replace-with to swap in another one. For example, om.mycompany.client.ui.CssGradientUtil.getLinearGradient could be a static method that looks like
CssGradientUtil util = GWT.create(CssGradientUtil.class);
return util.getGradient(...);
To make that work, have getGradient be a non-static method, overridden in CssGradientUtilIE7. GWT.create will go through the rebind rules and create an instance that fits best, and you can use normal java inheritance to get the overridden method.
There is no need for the first replace-with block, that replaces a class with itself.