java.lang.NoClassDefFoundError: Could not initialize class org.apache.cxf.interceptor.MyCustomInterceptor

Issue

When invoking a CXF based service which is configured for a custom CXF interceptor, the invocation randomly fails with
java.lang.NoClassDefFoundError: Could not initialize class org.apache.cxf.interceptor.MyCustomInterceptor

This always happens on the first and subsequent requests after a container restart. If the first request succeeds, then all subsequent invocations succeed as well.
The only way to resolve the error is to restart the Karaf container and hope that the first invocation of the CXF service succeeds.

The full call stack of the error reads

java.lang.NoClassDefFoundError: Could not initialize class org.apache.cxf.interceptor.MyCustomInterceptor
        at org.apache.cxf.phase.PhaseInterceptorChain.doIntercept(PhaseInterceptorChain.java:308)[217:org.apache.cxf.cxf-core:3.1.5.redhat-630347]
        at org.apache.cxf.transport.ChainInitiationObserver.onMessage(ChainInitiationObserver.java:121)[217:org.apache.cxf.cxf-core:3.1.5.redhat-630347]
        at org.apache.cxf.transport.http.AbstractHTTPDestination.invoke(AbstractHTTPDestination.java:254)[231:org.apache.cxf.cxf-rt-transports-http:3.1.5.redhat-630347]
        at org.apache.cxf.transport.http_jetty.JettyHTTPDestination.doService(JettyHTTPDestination.java:234)[232:org.apache.cxf.cxf-rt-transports-http-jetty:3.1.5.redhat-630347]
        at org.apache.cxf.transport.http_jetty.JettyHTTPHandler.handle(JettyHTTPHandler.java:76)[232:org.apache.cxf.cxf-rt-transports-http-jetty:3.1.5.redhat-630347]
        at org.eclipse.jetty.server.handler.ContextHandler.doHandle(ContextHandler.java:1129)[121:org.eclipse.jetty.server:9.2.23.v20171218]
        at org.eclipse.jetty.server.handler.ContextHandler.doScope(ContextHandler.java:1065)[121:org.eclipse.jetty.server:9.2.23.v20171218]
        at org.eclipse.jetty.server.handler.ScopedHandler.handle(ScopedHandler.java:141)[121:org.eclipse.jetty.server:9.2.23.v20171218]
        at org.eclipse.jetty.server.handler.ContextHandlerCollection.handle(ContextHandlerCollection.java:215)[121:org.eclipse.jetty.server:9.2.23.v20171218]
        at org.eclipse.jetty.server.handler.HandlerWrapper.handle(HandlerWrapper.java:97)[121:org.eclipse.jetty.server:9.2.23.v20171218]
        at org.eclipse.jetty.server.Server.handle(Server.java:499)[121:org.eclipse.jetty.server:9.2.23.v20171218]
        at org.eclipse.jetty.server.HttpChannel.handle(HttpChannel.java:311)[121:org.eclipse.jetty.server:9.2.23.v20171218]
        at org.eclipse.jetty.server.HttpConnection.onFillable(HttpConnection.java:258)[121:org.eclipse.jetty.server:9.2.23.v20171218]
        at org.eclipse.jetty.io.AbstractConnection$2.run(AbstractConnection.java:544)[113:org.eclipse.jetty.io:9.2.23.v20171218]
        at org.eclipse.jetty.util.thread.QueuedThreadPool.runJob(QueuedThreadPool.java:635)[124:org.eclipse.jetty.util:9.2.23.v20171218]
        at org.eclipse.jetty.util.thread.QueuedThreadPool$3.run(QueuedThreadPool.java:555)[124:org.eclipse.jetty.util:9.2.23.v20171218]
        at java.lang.Thread.run(Thread.java:748)[:1.8.0_131]