Kobra,
I must have missed the one where Dr Byte talked about the SMTPAUTH bypassing everything as it is the one that worked. The whole thing was just odd, how it was working fine under PHP, the ISP did no changes and it just failed. I actually thought maybe it was a corrupt file or more. To anyone reading this, the SMTPAUTH is the way to go if you can. Also, get 'real' hosting as I used to be on super cheap hosting like GD and it's easier to pay extra and have your site WORK than all the headaches that come with it.

Thanks and sorry!