Fix Linked Server Without Restarting SQL Server Instance
Depending on the statement you are running and how you have your linked servers configured, you could be running into a situation where you have an orphaned distributed transaction sitting out there that you need to kill.  To identify if this is the case or not, first run the following query:

SELECT  DISTINCT request_owner_guid
FROM    sys.dm_tran_locks 
WHERE   request_session_id = -2


If this returns records, chances are good that you are in fact running into this very situation.  To kill these orphaned transactions, you have to run the following statement for each record returned by the query above:

KILL 'UOW'


UOW is the request_owner_guid returned in the above query.

I've run into this situation with both linked server issues and jobs that are making calls externally from the SQL Server process.  In either case, I would find that an external process would interfere (e.g. network drop, process is killed or errors unexpectedly, etc.) and then the transaction wouldn't properly terminate at the SQL Server.  SQL Server won't know that the transaction has actually failed and things will just sit out there until you either walk through this process or bounce the server as you are already doing now.

Hope that helps.