So how do you make an updater be less horrible.
First off, as I suggested for all applets, consider not having one at all. For instance, Collectorz.Com's applications each check for updates periodically when they are started. That way you bury your update functionality with the application, and it alleviates the need to worry about external updaters.
If your application is itself a plugin (think Flash, Quicktime, Java or a driver (of any kind)), then you don't have a convenient application on which to hang your updater. For that case, whatever you do, don't burn a process whose sole purpose is to check for updates once a month. Instead, use the task scheduler functionality built into Windows to schedule your updater. The task scheduler is a remarkably flexible mechanism for scheduling periodic operations. Even using the Task Scheduler 1.0 interfaces (which are available on Windows platforms going back to Windows ME), you can generate triggers that will cause tasks to be run daily, weekly, monthly, monthly on a specific day of the week, logon, idle, etc. For Vista, the list of trigger types is enhanced to include triggers on system events, groups of triggers, etc.
One of the cool things you can do with scheduled tasks is to specify the context in which the job runs - jobs can be scheduled to run in the context of the user at the console, in the system context, the context of an interactively logged on user, to run only if a specific user is logged on, etc.
Using the task scheduler means that you can get your updater to run without consuming any long-term resources.
Once you've decided that you need to update the application, you've got to download the update. For that, you really have two options. The first is that you can assume that the user is going to want the update and pre-download it, the second is that you download it after informing the user about update. For either case Windows has a nifty feature called "BITS" which allows you to download data from the web without interfering with the user - essentially the BITS service is aware of the traffic generated by the interactive user and it throttles its transfers if it detects that the user's using the network. It also supports progressive downloading so it can handle the network dropping out mid transfer. Windows Update's downloader is built on top of BITS, but I'm not aware of any 3rd party apps that use it (which is a shame, because it really is cool). BITS is available on at least Windows XP and later, so it's not "yet another vista-only feature".
Also, whatever you do, don't ever require elevation for your updater - I cannot imagine any scenario that would require that your updater run elevated - it just annoys the user who complains about unnecessary elevation prompts.
Next: Mitigations for notification area handlers.