The reason is right there, in the DispatcherServlet class; it sends error response without bothering to call exception handler (by default).
Since 4.0.0.RELEASE this behaviour can be simply changed with throwExceptionIfNoHandlerFound parameter:
Set whether to throw a NoHandlerFoundException when no Handler was found for this request. This exception can then be caught with a HandlerExceptionResolver or an @ExceptionHandler controller method.
XML configuration:
<servlet>
    <servlet-name>rest-dispatcher</servlet-name>
    <servlet-class>org.springframework.web.servlet.DispatcherServlet</servlet-class>
    <init-param>
        <param-name>throwExceptionIfNoHandlerFound</param-name>
        <param-value>true</param-value>
    </init-param>
</servlet>
Java-based configuration:
public class AppInitializer extends AbstractAnnotationConfigDispatcherServletInitializer {
    void customizeRegistration(ServletRegistration.Dynamic registration) {
        registration.setInitParameter("throwExceptionIfNoHandlerFound", "true");
    }
    ...
}
Then NoHandlerFoundException can be handled like this:
@ControllerAdvice
public class GlobalExceptionHandler extends ResponseEntityExceptionHandler {
    @Override
    ResponseEntity handleNoHandlerFoundException(NoHandlerFoundException ex,
            HttpHeaders headers, HttpStatus status, WebRequest request) {
        // return whatever you want
    }
}