MX Records

I setup my MX records a while ago (3 weeks) and people are complaining that they get some emails bounced. I checked with the domain registrar and the MX record are looking fine. If I do an nslookup, the MX records are pointing to wrong address. Any ideas how to fix this issue?

Any help would be highly appreciated.