I would check out other hosts as well, several hosts would probably fit your needs. I wouldn't decide on a host just because they offer several hundred GB's of diskspace and bandwidth.
For one I had this experience. What do you guys think of those hosting with "unlimited bandwidth, storage, mysql" etc?!
Ahhhh, that is a tough call. The way I look at it, they may have used your service to shorten their URL, but it doesn't mean you actually run the spam site itself. That's a really sticky situation. I would consult with new companies, and see what their stance is. So if a spammer used a link, and you deactivated the link they used, it doesn't satisfy Godaddy? Of course, I think Godaddy is a butt for wanting you to pay $200 because of this issue. I know plenty of hosts that deal with this issue, and they don't charge that type of fee.