¿Quién dijo que enviar correos desde aplicaciones .NET es fácil? Tal vez cuando haces los ejemplos con tú máquina, pero cuando empiezas a trabajar con hoster, que va, ya no es "ezy"....
System.Web.Mail, OH MY! aunque no me resolvió el problema, me dió una ayudadita para entender todo esto del envío de correos desde aplicaciones .NET.
Al final lo resolví usando CSLMail, un componente que encontré en WinToolZone. Simple, sencillo y efectivo, lo único es que no viene con código fuente, pero al fin y al cabo, deje de sufrir con el envío de correos :D