Here's my old school setup:
Deployment: `easy_install -U` from a local pypi
Packaging: `setup.py bdist_egg` and `setup.py bdist_wininst`
Dependencies: declare in setup.py, fetch via yolk
To test if everything works, just create a blank virtualenv and easy_install.
This has been working fine for me for years on Linux and Windows.