I thought I had the same problem once. Strange thing is I could send an email to some people but not to others. It turned out the problem was I misspelled my return address. Some people sat behind gateways that checked the validity of the domain the email came from and rejected mine.

Another obvious question is, are you sending it via WiFi or GSM/3G? If the latter, then you are not comparing like for like. The PC and the N900 are using different ISPs.