I was taught that but and the adverb showing contrasting ideas ,such as nontheless, nevertheless and the like, should not be used in the same sentence because it tends to make the sentence redundant.

However, I found the sentence like the one below very frequently:

We should be thankful that Osama bin Laden's intervention in our election took the form of a videotape, and not an attack, as in Madrid on March 11. But it was an attempted intervention nonetheless.

What should be the rule that the usage of "but...nonetheless" is juistified?

It is entirely possible for the conjuncts "nevertheless" and "nonetheless" to co-occur with "but." According to the Longman Dictionary of Contemporary English, New Edition (2003), they mean "In spite of the fact that has just been mentioned."

Quirk et al.* give the following list of conjuncts that can co-occur with the coordinators "and" and "but":

Besides
then (again) [antithetic]
still
yet
nevertheless

To this list we should add "nonetheless," a more formal but rarer alternative to the already formal "nevertheless." The conjunct "however," on the other hand, is not included in this list. (p. 645)

Here are a few Google examples of the co-occurrence of "but" with "nevertheless" or "nonetheless":

"” If you are connected by modem, the films will be a bit small, but you can see them nonetheless.

"” My doctor has said that I haven't had a stroke because I haven't had any other major symptoms but I nevertheless worry about it because of the pressure.

"” Unfortunately these facial swellings won't make an exciting episode of ER but they can be deadly,nonetheless.

"” I may not agree with much of what Heston stands for, but I can nonetheless feel deep compassion for him as a fellow human being.

"” "The first flight lasted only twelve seconds, a flight very modest compared with that of birds, but it was, nevertheless, the first in the history of the world."

"” From time to time, we post programs here that we've written, which don't fit naturally into our other products, but which we find useful nonetheless.

"” There is also a spiritual angle to community development. The spiritual component is a bit more difficult to pin down, but it is nevertheless important.

"” We never actively seek press attention, but sometimes we attract it nonetheless.

Sometimes the word "still" is added:

"” If you have an open relationship with your child, these conversations are easier, but they can nonetheless still be challenging.

"” The two-plus hour run time is not a problem, but the film fades quickly after you leave the theater. I continue to like Witherspoon and have increased respect for the talented actress. "Vanity Fair" is like flavored popcorn – tastier than regular popcorn but it is still popcorn, nonetheless. I give it a B-.

Marilyn

*A Comprehensive Grammar of the English Language (Longman, 1985)