Don't bring a gift; don't call and ask
This is an opportunity to teach your son three very important lessons:
1. Your beliefs are not more important than their beliefs.
While it may be tempting to give the gift anyway, or try to persuade them to accept the gift, that really isn't respecting their beliefs. If you give the gift, you're forcing your belief on them. If you try to persuade them, you're trying to change their beliefs. If you really want to respect their decision, you will abide by their request and let it go.
2. People are not required to explain their beliefs to you.
Calling them is only going to make them give reasons (which may or not be real reasons, but just ones they chose to advertise) that they should never have to give in the first place. They have no obligation to defend their decision to you, or to make an attempt to compromise.
3. Other disrespectful people don't make it okay for you to be
Other people may have brought gifts in the past and had no incident. They willingly chose to disrespect the stated beliefs and enforce their own. Now perhaps the people who did it were well respected in the family or community, or were key business people who would be incredibly offended if the gift was declined (not to mention ruin the mood for the party), so there may have been no incident, but that doesn't mean they didn't just stuff their feelings down inside for the sake of the birthday party.
Let's put a slightly different spin on your situation. Time for some role playing.
Imagine a boy (let's call him Johnny) growing up in a family of alcoholics. He decides he's going to avoid the pitfalls of his family and abstain from all alcohol. Fast forward to college, and he's going to university with your son. His status as a strict-non-drinker is known to your son. Some friends ask your son if he's coming to have a couple drinks with them. Your son and his friends are very responsible drinkers. They don't get completely smashed and go keying cars, no trouble with the cops, and have no problem getting up to go to work the next day.
Your son's friend says "hey, is Johnny coming?"
This is literally the exact same scenario. Now, generally we consider giving gifts to be a "good thing" and drinking to be a "bad thing", but we know that gifts can definitely be bad, and that drinking can be good, it all matters on how far they are taken in both regards.
Johnny has a right to not drink just as much as your son has a right to drink. Just because your son has no problem having a couple beers and staying responsible doesn't mean he has to force it on his friend who willing chooses not to. If your son wants to respect his friend, he just won't ask him to come since he already knows the answer. Putting him in a situation where he has to say no would probably be embarrassing and difficult.
Johnny is not required to give a reason why he declines an invitation to go drinking. He's not required to go along and DD (although many would consider it a good compromise to avoid social ostracization, he shouldn't have to feel pressured to). And if your son wants to respect his friend, he won't ask his friend to defend his decision not to go. Putting him in a situation where he has to would probably be embarrassing and difficult.
Johnny should not have to feel pressured just because others who chose not to drink have changed their mind and still been responsible drinkers. Not that it's any weakness on their part necessarily, but this is just a form of pressure that a friend shouldn't put on another friend. (Ultimately, that anyone should put on anyone anyway...) This is a straw-man argument to persuade Johnny to come along (a debate that shouldn't even be happening in the first place).
Now, in this case Johnny is like the parents who sent the "no-gift's" invitation. The reactions we would get from the Johnny situation are so obvious because they've been drilled into our heads that we need to avoid peer pressuring friends into drinking and doing drugs, and specifically that we need to learn to resist those pressures. Those principles don't change just because drinking or drugs aren't the subject matter.
Whether the belief is something as important as the existence of God, or something as trivial as light rain showers are pleasant, if we really want to respect other people's beliefs we should follow these three lessons.