What do you use to produce dpkgs? In addition to the cumbersome standard tools, I'm only aware of jpkg (http://code.google.com/p/jpkg-library/) for Java.

I've found the dpkg method to be very effective. You can sign the packages, mirror the repositories, and set up servers to automatically upgrade some/all of the packages via cron jobs.

Packages can be automatically generated by your continual integration system, which also has the nice effect of creating a fully-trusted and centralized deployment path, making it difficult to sneak in uncommitted changes and non-managed files, etc.

The packages themselves support complex dependencies, start/stop scripts, etc, and dpkg/apt-get themselves have been ported to non-Linux platforms.

Personally, I'd still like a more comprehensive centrally managed solution based around the packaging model (ie, each server runs a management agent that can install/remove/update packages, etc).