Short answer: 400-800 pixels.
What I have read is that HTML newsletter width should be as narrow as possible without being too narrow. For instance, 400-500 pixels for a one column layout is a lower limit. Any less may look too weird.
Today's widescreen monitors allow for more horizontal pixels and most web email clients will either be of the two-column variety (Gmail) or 3-pane layout where the content window bellow the inbox list (Hotmail and Yahoo). In either case, you can be okay with 800 pixels if you're targeting the 1280 wide audience. An older or less technical audience may have older, square monitors.
There is the problem of Outlook having a three-column layout. That limits the width of your email even more. With them, you may want to go even narrower.
I just recently created a template that required an ad banner that is 730 pixels wide. It was near in the wide range, but not so much that most people could not double-click the email an open a new window in Outlook (the web email users should be okay for the most part).
Hope this advice helps.