Another option using a Possible Worlds account is to interpret "possible" and "impossible" slightly differently, making use of alternative Modal Logics for the box and diamond operators. These can still be worked into discussions about possible worlds, but the semantics of how these worlds are related to one another becomes a little more intricate.
The analysis of "impossible" you've used employs a quantification over every world in our domain of worlds. Some modal logics, however, don't treat necessity and possibility as absolutely general quantifiers in that way. Saul Kripke's weak modal logic K, for instance, adds only three basic rules to an underlying propositional logic which seem to capture some basic intuitions about necessity and possibility:
Necessitation: If A is a theorem of K, then so is □A
Distribution: □(A→B) → (□A→□B)
Duality: ◊A = ~□~A
(Distribution can be read as "If it's necessary that A follows from B, then if A is necessary then so is B")
In this logic, thinking of "Necessity" as something being true in all possible worlds doesn't quite match up perfectly. For instance, if that were the case, then we should expect that:
Localization: (□A)→A
That is, that if something is necessary then it is in fact true. But system K can't prove this, since its axioms aren't exclusive and exhaustive about what kinds of things are necessary (merely affirming that theorems are among the necessities)
What do such logics really mean, in a metaphysical sense? Well, Kripke's way of interpreting the weaker logics builds on the possible worlds model through the use of Frames. In Frame semantics, we have as before a set of possible worlds, but also a binary relation over the set of worlds which we call Accessibility. The idea here is that at each base possible world, some of the other worlds are accessible to it. What is possible at a base world is something that obtains at one world that is accessible to that base, and what is necessary at a base world is something that obtains at every possible world that is accessible to it.
In the case of standard (S5) Modal logic, we use a trivial accessibility relation such that every world is accessible to every other world, and so possibility and necessity quantify over all worlds. We can also use Frame semantics to account for weaker modal logics by trimming down what is accessible to any given world, or justifying the addition of new axioms by arguing for certain qualities for an accessibility relation. For instance, if we stipulate as a requirement that our accessibility relation is Reflexive (that any possible world w is always accessible to itself) then we'd have a model satisfying Localization.
In this way, we can see some models where something might be possibly impossible, but not actually impossible. Consider for instance the case of three possible worlds, w1, w2 and w3, where all worlds are accessible to themselves, and w2 and w3 are both accessible to w1 but not to each other. If we are at w1 where a proposition p is false, and p is also false at w2 but true at w3, then we can see that p is possible at w1 (because it's true at w3). However, since w3 is not accessible to w2, then at w2, p is impossible. So at w1, p is both possible and also possibly impossible.
