You could always provide your own package repository and/or build your own packages. It's not terribly difficult, and certainly isn't any more difficult that maintaining your own auto-update mechanism anyways. And if you have your own package repo, users will get updates from your repository whenever they update their system...
You still have the problem of having your package's dependencies be broken/mutilated/ancient -- the only solid way to get around it is to statically link with your own unfucked builds, but that isn't always possible.
