This has nothing to do with open relays as far as I can tell. It also doesn't have to do with authentication or anything like that. Your users are simply receiving spam that has forged From: address and smtp envelope sender. It's very easy for this to happen--the spammer just harvested the addresses from a website, or tricked users into entering the addresses into web forms, or received the addresses from the contact list on a computer that was infected. That computer could be the personal computer of someone in your organization, or their work computer, or it could be the computer of an external colleague.
This is your key line:
Reading forward through the Received lines shows it's genuine.
Received: from ABTS-North-Dynamic-074.230.173.122.airtelbroadband.in (unknown [22.214.171.124])
by example.com(Postfix) with SMTP id 720DDD4195
for <email@example.com>; Tue, 10 Aug 2010 12:21:58 +0530 (IST)
There are two relatively easy things you can do. One is to make use of more RBLs, either for scoring or for blocking at the MTA. For example, if you'd used b.barracudacentral.org, the spam would have been caught:
barracudacentral is so reliable that I'm comfortable using it to block at the MTA. Other RBLs, you might want to create custom rules in salocal.conf.in. Just search the forums--I'm pretty sure you'll find examples, by me and Uxbod, among others.
% host 126.96.36.199.b.barracudacentral.org
188.8.131.52.b.barracudacentral.org has address 127.0.0.2
The other thing is to just reduce your "Required" spam score. You've got it at the default of 6.6 (33%). I would reduce it somewhat based on your observation of the scores of some legitimate mail coming from outside and some spams that got through. Personally, I use 4.4 (22%).