I think from memory this issue can be caused to not having this set up using the Episerver IInitializableModule way. I believe if you are using Find there can be some conflicts with the loading order, although this is off the top of my head. Try putting it in an initalization module such as the following example

/// <summary>
    /// The WEB API Configuration class
    /// </summary>
    [InitializableModule]
    [ModuleDependency(typeof(FrameworkInitialization))]
    public class WebApiConfig : IInitializableModule
    {
        public static string ApiRoute = "api";

        public void Initialize(InitializationEngine context)
        {
            // Enable Web API routing
            GlobalConfiguration.Configure(config =>
            {
                // Attribute routing
                config.MapHttpAttributeRoutes();

                var formatters = GlobalConfiguration.Configuration.Formatters;
                var jsonFormatter = formatters.JsonFormatter;
                var settings = jsonFormatter.SerializerSettings;

                var enumConverter = new Newtonsoft.Json.Converters.StringEnumConverter();
                jsonFormatter.SerializerSettings.Converters.Add(enumConverter);

                settings.Formatting = Formatting.Indented;

                config.Formatters.Remove(config.Formatters.XmlFormatter);

                // config.MapHttpAttributeRoutes();

                config.Routes.MapHttpRoute(
                    name: "DefaultEpiApi",
                    routeTemplate: ApiRoute + "/{controller}/{id}",
                    defaults: new { id = RouteParameter.Optional });
        }

        /// <inheritdoc />
        public void Uninitialize(InitializationEngine context)
        {
        }
    }

Thank you so much, Scott, this worked! Do you know why I had to do it this way here, and not in the other projects?

I believe there's a conflict with Episerver Find's own APIs where the configuration.MapHttpAttributeRoutes(); is called in one of these modules and it has an issue if you try to call it twice in the wrong order. By adding the IInitializableModule with the FrameworkInitialization you're making sure this is called after and so it doesn't have the conflict. As far as I remember this is the case anyhow :-)

Ok, I see. I don't use Find, only EPi Search, but i guess there is something causing the same issue. Thanks again

Ah I see, yeah I think as they both expose the same APIs for the CMS/Commerce search facilities they wouldn't probably be doing the same thing. No worries, glad it works :-)

For me I got this when using Marketing (A/B-testing) addon or the service-api since those AddOns does not use the initi... the correct way and have forced in the routing before you do it.

But the way Scott describes works and that is the way we do it also

Aha, we have the A/B testing addon, so it's probably the one causing the problem.