<p>And how to fix it. I'd like to log every thrown exception for maintenance purpose.</p>

This is a known issue in .Net - Application_Error never fires for a web service. Not sure if there's any reason it would be by design, but it just doesn't work.
Jeff Atwood had a
post
(and
follow-up
) about this a few years ago, with the following ideas:
Put a try-catch block around each web service method
Use a facade design pattern and include the try-catch in parent objects
Write a custom SOAP extension or HTTPModule
The only one I care for is the first one, even though it seems like a lot of work.