As I've written about recently, the term "Inversion of Control" has come to be closely associated with "Dependency Injection". Indeed many people tend to use the two terms interchangeably. The reality is that DI is just one way of achieving one kind of limited IoC.
It's worth considering that something cannot be inverted without there being an original, un-inverted state. So what is that state, and why did it become so important to invert it? According to Martin Fowler's Bliki post on IoC, the state in question is which code is in control of the flow of the program within a particular scope. Fowler credits Ralph Johnson and Brian Foote's 1988 paper Designing Reusable Classes, with originally identifying the boundaries between system layers, or between a framework and the consumer of that framework, as being particularly valuable places to invert control.
The goal of the inversion, as stated by Fowler, Johnson, and Foote, is essentially to let a service remain in control of the pieces of its execution, rather than to micromanage it from the outside, like a boss who insists on being kept "in the loop". I would say this is dramatically different from what IoC has come to mean in the common parlance today.
IoC in its common usage has become divorced from the Hollywood Principle, which was about allowing a service to retain control of its own execution. Instead it has been married to DI, which is about a service divesting responsibility for ancillary concerns. The latter is equally important. But only equally. When they are brought together, they enhance each other and the resulting clarity of the design is more than the sum of its parts.
There is a duality here that is important to keep in mind when designing classes and interfaces. A duality of scope, a duality of perspective, a duality of responsibility, a duality of control. There is both give and take. By giving one thing, we take another. IoC is not just about giving up control and responsibility for choosing and creating dependency implementations. It's also about taking control and responsibility for the cohesion of the solution, the algorithm, and the facade that's offered by a service, a framework, or a layer.
It is far too easy, when one first delves into DI, especially aided by the power tool that is an IoC container, to forget this other side of things. We become satisfied that as long as we don't have a "new" in our constructor, we must be on the right track. But sooner or later you will end up in a situation where the discipline of DI becomes very difficult to maintain. Without the context of where DI came from, the limits of its purpose, and the parallel concerns that were meant to be addressed alongside, it won't be clear what is the proper way to proceed. You may realize that it's time to "break the rules", but you won't know what new rules then take over.
Speaking from experience I can tell you that this way lies madness. Or at least messiness. Potentially maddening messiness. Far too many people simply shed the rules as they pass this boundary and revert back to wild and woolly frontier-style programming. But the truth is that you aren't passing from civilization into the wilderness. You may be leaving one regime, but you're also entering another. And the guiding light of this new regime isn't just "whatever works". Most likely it's simply time to broaden your perspective beyond the issue of class dependencies and Separation of Concerns.
Start to look at the surface of the layer, model, framework, or module that the problem classes are a part of. Consider all of its responsibilities, dependencies, entry points, hooks, and outputs. If you are encountering problems making DI work, it's very possible that a mess has begun to accrete in one of these other aspects. If you step back to get the broader perspective, it may be easier to identify the problem as a flaw in the cohesion of it as a whole.
In particular, look at the ways your objects are working together, and the way the whole layer interacts with its consumers. A clear story should show up somewhere. Yes you may have a hundred small classes running around taking care of little chunks of the work. But someone should be "conducting" these bits as they work together to accomplish the goal, and that someone should be chosen and designed deliberately.
It's a common mistake to break responsibilities down into bits and then just toss them all together with no real clear roadmap emerging from the noise. This is a real problem, and the cause is a proliferation of delegation in the interest of decoupling, combined with a failure to take the reigns of regional control that ensures cohesion. Weaving together the dual needs of decoupling and cohesion is what Inversion of Control is really about.