This package makes reference to EMACS_VERSION_MAJOR, as apparently it
  can according to emacs.mk.

I took a brief look, as I had trouble with having emacs22 installed and
EMACS_TYPE was defaulting to emacs21.  (I think this is a bug;
editors/emacs and EMACS_TYPE default should match.)

My quick reaction is that having these kinds of conditionals is messy,
but I see why it's needed.

  There is a problem though.  EMACS_VERSION_MAJOR is determined by
  looking at the Emacs package that is currently installed.  There isn't
  one installed yet though.  So it adds a dependency and continues, but
  EMACS_VERSION_MAJOR is left unset.

That's buggy.  If EMACS_VERSION_MAJOR is ever going to be set, it should
be set consistently, and that means either the installed version, or the
version that was just added and will be installed.  So maybe all
emacs-providing packages need a version.mk that emacs.mk includes.

But, the whole notion of EMACS_VERSION_MAJOR is itself broken.  Is 21
emacs or xemacs?  Is it really reasonable to want 'version 4 or higher
of IE or netscape', ignoring that they are separately maintained?

So perhaps instead doxymacs should switch on EMACS_TYPE, adding w3 if
the type is in an allowed list.

Even further, it's wrong to encode information about which versions of
emacs w3 works with in other packages.  So probably there should be some
mk fragment in w3 that includes w3 either unconditionally (provoking
failure), or conditionally (adding if it should).

Sorry if I sound cranky - I hope this is helpful.