<p>ASP.NET ASMX service occasionally throws exceptions. However, global.asax Application_Error method do not seem to catch them. The question is, how to configure global error handler to catch and log these exceptions?</p>

Is it the ASMX or the AJAX JavaScript which is throwing the exception?
If it's the Javascript, you'll need to write exception handling into your JS, and then push that back to the server to be tracked in your error datastore--possibly via another call to your webservice.
If it's the ASMX then it's probably getting caught by your Application_Error, BUT as ASMX returns XML or JSON it won't necessarily get displayed on your UI unless you're looking for it.