Based on the support ticket I post the answer in here as well.
You are correct that this will be problem to troubleshoot as the way how the payement gateways work within Kentico is that We are using POST method to post data in following parameters to Authorize .NET provider:
And there is only a response code returned from the gateway back to application.
In this case you could implement custom payment gateway, that is actually the same as the default authorize.Net gateway:
Than you can add some EventLogProvider.LogEvent() method to log certain details that could help you find the problem.
Other option is to use traffic monitoring tool (e.g. Fiddler: http://www.telerik.com/fiddler) to track posts and responses to see if there are any issues with data posted.