We recently had the same issue in SQL2005 that did not go away after SP4... Once we upgraded to Cumulative update 3 for SP4 the error went away... So there...