It is do-able. Because MXM always outputs 640x480, you'll get best results if the input is also 640x480 - that means a 640x480 (4:3) skin that will look 'right' when the TV stretches it to 16:9.
To get there, I'm pretty sure the best way is to design all the bits of your skin with a final size of 853x480 (16:9) in mind, making them look right at that size. Then, when you've really finished in Photoshop or wherever, scale the artwork to 640x480, making sure you let the image editor 'squeeze' the image (ie don't constrain the proportions). That gives you a 640x480 skin (so MXM doesn't have to do any scaling) that looks wrong in 4:3, but will look right when stretched to back 16:9 by the widescreen TV.
I think you should be able to get thumbnails and preview videos to look right as well by getting MXM to squeeze them so they look right again when stretched by the TV. There isn't, I don't think, anything you can do about the text because you can't squeeze it in MXM - the best you can do is pick a narrow font that looks OK stretched 1.33 times its original width.
Using DVD's 720x480 (in NTSC land...) introduces another variable (it means MXM has to scale your skin down to 640x480 before it gets stretched by the TV) which makes it very difficult to know how the design is going to look on the widescreen TV. 720x480 only gives you widescreen 16:9 because it's 720x480 non-square pixels, whereas pretty much every still image editor (eg Photoshop) is square pixel only.