Had this issues when I tried to deploy a BizTalk 2004 assembly to a recently patched SQL 2000 SP4 Instance:
[Microsoft.BizTalk.Deployment.DeploymentException] [System.Data.SqlClient.SqlException] Failed to load msxmlsql.dll. [System.Data.SqlClient.SqlException] Failed to load msxmlsql.dll.
A few sites pointed to potential fixes but these appeared to be red herrings. In the end our DBA re-applied SP4 and the issue was cleared up. Most bizarre. Will teach us to deploy security updates so quickly!