Ever think it could be your camera that is causing this 'bad marriage'? I'm just saying that when people talk about 'bad lenses' they conveniently ignore the fact that the camera also plays a very BIG part in the focusing equation...
Just like Noah, I have "two of each" and many a time one of my lenses works perfectly well (or only needs a little AF microadjustment) on body A but can't be made to work (i.e. achieve sharp images) on body B.
Did you try this lens on another camera? If you did, I missed it in the many replies and posts, if you didn't it might be worth your while to try it.