Nothing in the coding you can really do about it - but you're right it can degrade gracefully! Something like putting the large orange image in a transparent PNG and just embedding it as an image, and then putting the black/orange fade as a body background image. Of course, then you have to combat IE6 which a lot of users still use
There is a fix with Outlook 2007 background images actually, and also a fix to get around Gmail cutting out the body tag (msg me if you wanna find out)
I tend to code all emails table-based and styled inline - it's the only way to ensure the design shows consistently across clients. In coding this particular email the only background images you'd have to worry about would be the design elements behind the text - everything else is workable with flat jpegs and gifs.
I am interested in those workarounds you mentioned though... *runs off to message you*