I've looked at this some more using variations of Alexy's test case and I now think there are at least two problems here.  And both issues have to do with confusion about exactly where a distribution's header files should be installed in venvs (created with the standard library venv) or virtual environments (created with the third-party virtualenv).

One, when building an extension module from a venv, py3 Distutils tries to add the path of the venv include directory to the list of include directories supplied to the C compiler front-end.  However, build_ext assumes that the include files have been installed in venv/include (Lib/distutils/command/build_ext.py#l157) while install.py uses an "install scheme"-specific location to install headers (Lib/distutils/command/install.py#l22); for unix non-user installs, that may be something like venv/include/python3.5m.  This is particularly a problem for a situation like here where the build of an extension module from one distribution, uwsgi, is dependent on the header files for an extension module from a previously installed distribution, greenlet.  So, to resolve this, it seems like build_ext needs to be smarter about the include path for venvs.  There should also be test case(s) to ensure that install_headers and build_ext are using the same paths in all relevant environments, e.g. venv, non-venv, user install, Windows, etc.

But even if that is fixed, there is another issue.  It appears pip uses yet another location for installing distribution header files in virtualenvs and venvs: venv/include/site/python3.5. So, if pip is used to install the distribution supplying the include files, the dependent distribution will still fail to build.  From the deleted comments in a recent commit (https://github.com/pypa/pip/commit/882cd358d1abd5e42df6333dddc42f52ab7d6ff2), it appears the reason why pip does this is that virtualenv creates a symlink to the interpreter's global include directory which means that include files from distributions installing to the virtualenv cannot be written to the normal (non-virtualenv) path.  It also looks like venv does not create such a symlink but depends on Distutils build_ext to supply paths to both the venv include directory and the global include directory to compilers.  I'm not sure what the right solution is here and I certainly may be missing something.  In any case, it must be possible for distributions to find the header files from other distributions regardless how they were installed.

Since these are all packaging issues, I think the PyPA folks need to take this and decide what action(s) are needed where.