Debugging MSDTC problems can be a bit painful. You said it is running, is it running on both servers? Are there firewall(s) between the servers -- you have to make sure each server can DTCPing the other one. DTCPing is a MS utility you can download. You can have permission problems too.
DTC performance can be pretty awful at times, but this is usually due to bandwidth and roundtrip time issues or memory consumption if the transactions are large. As far as I know, it is always slower than the non MSDTC equivalent -- assuming that they are actually equivalent
Personally, if I can rewrite the query to avoid MSDTC completely, I am usually happier with the result. If you insert the output of an exec proc on the remote server, MSDTC will always be invoked.
No real advice on the random timings, perhaps if you explained in more detail.
Added info on DTC Ping from this article
DTCPING makes anonymous RPC call to remote machine
from xp,sp2,by default,remote machine won't accept anonymous calls,so it is giving you access denied error message (OX5 error code)
if you disable RestrictRemoteClients key,remote machine accepts anonymous calls
http://msdn.microsoft.com/security/productinfo/XPSP2/networkprotection/restrict_remote_clients.aspx
This is just DTCPING tool problem,This error is not related to DTC.