I'm from the western U.S. and the phrase "Not at all," when used in its most common fashion, is not rude. In fact, in its most common use, I disagree that it's stronger than "no." In our culture, it's simply formal and polite. It's similar to saying de nada (it is nothing) in Spanish, which I hear said all the time by my Spanish-speaking friends.
It should be noted that the phrase in our region is most commonly heard when the negative response has a positive connotation.
Would you mind passing the salt?
Not at all!
Compare the same statement with the shorter, more terse "no."
Would you mind passing the salt?
No.
In a situation like that (and in our region), using "no" sounds more dismissive, suggesting the person asking the question deserves little or no attention. However, I admit that the distinction is mighty thin and could be more reflective of my social group than my region.
However, compare this with a negative response having a negative connotation:
Will you help us?
Not at all.
In this case the response would be very, very rude.
Let me leave you with one more idea, and it's kinda contrary to a statement I made earlier. When used in its most common fashion in my region, the phrase isn't stronger than "no." However, I believe it is fair to say the phrase can be thought of as an "emphasis," a verbal way to place an exclamation mark at the end of a "no." Thus, in a positive context it expresses enthusiasm to support the intent of the request.
Does this dress make me look fat?
Not at all!
But it also emphasizes the negative context.
Did you do your homework?
Not at all!