apt-get chosing packages that don't match depend constraints

[jtc@acorntoolworks.com (J.T. Conklin)]

At my workplace, we use semantic versioning (http://semver.org) to
help manage package dependencies.  Each of our package's Depends list
has both a floor and a ceiling set for each dependent packages. For
example, if version 1.0.0 of package "foo" is compatible with the API
from versions >= 1.0.0 and << 2.0.0 of package "bar", both the bounds
will be specified in foo's control file.

Unfortunately, this is not working as expected. When the package
repository has versions 1.0.0, 2.0.0, and 3.0.0 of package "bar",
"apt-get install foo=1.0.0" is not selecting a version of "bar" which
matches the contstraints specify by foo-1.0.0's Depends list. Instead
it appears to select the latest version, 3.0.0, only to complain that
it does not match the constraints.

For example:

    $ apt-get install -s foo=1.0.0
    Reading package lists... Done
    Building dependency tree       
    Reading state information... Done
    Some packages could not be installed. This may mean that you have
    requested an impossible situation or if you are using the unstable
    distribution that some required packages have not yet been created
    or been moved out of Incoming.
    The following information may help to resolve the situation:

    The following packages have unmet dependencies:
     foo : Depends: bar (< 2.0.0) but 3.0.0 is to be installed
    E: Unable to correct problems, you have held broken packages.

Manually installing version 1.0.0 of package bar and then installing
version 1.0.0 of package foo of course works, but that approach
doesn't scale to the number of packages and the more real-world
package dependencies that we really have.  

With that background, a couple of questions:

  * How much of a mismatch are my expectations of how apt-get should
    behave?  This seems like a use case that apt-get should be able
    to "solve" itself.

  * Are there any alternate ways to accomplish this?

    Whenever someone breaks a API and bumps the major version number
    of a package we go through enormous pain until all packages that
    use that component are updated. I forsee this getting worse. Very
    soon we'll need to support multiple parallel development streams.

Thanks in advance,

    --jtc