Intermittent NullReference Exceptions when creating Controllers

[gavinbarron]

We have an infrequent but persistent issue with Unity.

Once every few thousand requests or so Unity throws a NullReference Exception when the attempting to construct the controller

Now these are requests that work as expected 99.9% of the time, so It's not that we haven't registered the dependencies, which is what I'd expect with this specific exception and message. Frankly I'm more than a little puzzled and would love some pointers on how to track down our issue.
The fact that it's infrequent and unpredictable makes isolating the issue very tricky.

Top Level Exception: System.InvalidOperationException - An error occurred when trying to create a controller of type 'SettingsController'. Make sure that the controller has a parameterless public constructor.

   at System.Web.Http.Dispatcher.DefaultHttpControllerActivator.Create(HttpRequestMessage request, HttpControllerDescriptor controllerDescriptor, Type controllerType)
   at System.Web.Http.Controllers.HttpControllerDescriptor.CreateController(HttpRequestMessage request)
   at System.Web.Http.Dispatcher.HttpControllerDispatcher.<SendAsync>d__15.MoveNext()
   at System.Web.Http.Dispatcher.HttpControllerDispatcher.<SendAsync>d__15.MoveNext()
   at System.Runtime.CompilerServices.TaskAwaiter.ThrowForNonSuccess(Task task)
   at System.Runtime.CompilerServices.TaskAwaiter.HandleNonSuccessAndDebuggerNotification(Task task)
   at System.Web.Http.HttpServer.<SendAsync>d__24.MoveNext()

Inner Exception: Object reference not set to an instance of an object.
   at Unity.UnityContainer.<>c.<.ctor>b__73_2(BuilderStrategy[] chain, BuilderContext& context)
   at Unity.Builder.BuilderContext.Resolve(Type type, String name, InternalRegistration registration)
   at Unity.Builder.BuilderContext.Resolve(Type type, String name)
   at Unity.Builder.BuilderContext.Resolve(ParameterInfo parameter, Object value)
   at Unity.Strategies.BuildPlanStrategy.PreBuildUp(BuilderContext& context)
   at Unity.UnityContainer.<>c.<.ctor>b__73_2(BuilderStrategy[] chain, BuilderContext& context)
   at Unity.Builder.BuilderContext.Resolve(Type type, String name, InternalRegistration registration)
   at Unity.Builder.BuilderContext.Resolve(Type type, String name)
   at Unity.Builder.BuilderContext.Resolve(ParameterInfo parameter, Object value)
   at Unity.Strategies.BuildPlanStrategy.PreBuildUp(BuilderContext& context)
   at Unity.UnityContainer.<>c.<.ctor>b__73_2(BuilderStrategy[] chain, BuilderContext& context)
   at Unity.Builder.BuilderContext.Resolve(Type type, String name, InternalRegistration registration)
   at Unity.Builder.BuilderContext.Resolve(Type type, String name)
   at Unity.Builder.BuilderContext.Resolve(ParameterInfo parameter, Object value)
   at Unity.Strategies.BuildPlanStrategy.PreBuildUp(BuilderContext& context)
   at Unity.UnityContainer.<>c.<.ctor>b__73_1(BuilderContext& context)
   at Unity.UnityContainer.Unity.IUnityContainer.Resolve(Type type, String name, ResolverOverride[] overrides)
   at Unity.UnityContainerExtensions.Resolve(IUnityContainer container, Type t, ResolverOverride[] overrides)
   at Unity.AspNet.WebApi.UnityDependencyResolver.SharedDependencyScope.GetService(Type serviceType)
   at System.Web.Http.Dispatcher.DefaultHttpControllerActivator.GetInstanceOrActivator(HttpRequestMessage request, Type controllerType, Func`1& activator)
   at System.Web.Http.Dispatcher.DefaultHttpControllerActivator.Create(HttpRequestMessage request, HttpControllerDescriptor controllerDescriptor, Type controllerType)