I looked back in my notes last night. The situation I had faced was that I had a SQL Server 2005 x64 installed on a x64 version of windows server. Linked server queries would not work against SQL Server 2000 servers. This was only applicable to that particular combination (SQL Server X64 querying against SQL Server 2000 x86), all other linked server connections to the x86 server worked as expected.
After some digging, I found that the catalogs on the 2000 machine had not been properly updated by the service pack 3 application.
The solution was to manually run the instcat.sql file against the x86 SQL Server 2000 instance so that the x64 SQL Server 2005 instance could communicate with it.
The problem was with the listening end rather than with the calling end.
Since you have told us very little about your environment this still qualifies as 'just a thought'.
If you have not already, you may want to look at MS KB 906954 to see if it is similar to your situation.