Aha!
Maybe it indeed does have to do with version as the Debian policy manual [1]
states that
"If a relationship field has a version number attached, only real packages
will be considered to see whether the relationship is satisfied (or the
prohibition violated, for a conflict or breakage). In other words, if a
version number is specified, this is a request to ignore all Provides for
that package name and consider only real packages."
apt-cache show xul-ext-mozvoikko shows the dependency indeed contains a
version number:
Depends: libvoikko1, voikko-fi, firefox (>= 4.0)...
And apt-cache policy firefox shows the real package is not available.
firefox:
Installed: (none)
Candidate: (none)
Version table:
Case closed, dontcha think?
[1] http://www.debian.org/doc/debian-policy/ch-relationships.html#s-virtual