There is no big mystery here - the message you get back from everyone.net explains precisely why they will not accept messages sent from the particular place you're trying to send them. The problem IS the particular ISP you're using - it's just that all those you've tried have been blacklisted in a similar way.
It's got nothing to do with Nigeria particularly - it's just that if a particular ISP allows spam to be sent then it is very hard to know which person using that ISP is to blame, so the whole ISP gets blacklisted. If you fail to see why they do this I suggest you set up and manage your own SMTP server and let people use it for free.
The easy solution to the problem was already offered in this thread - use your Internet cafe's outgoing mail server. Then, if you wish, you can petition everyone.net to remove the blacklisting, though I doubt they will.