「ご丁寧にありがとうございます。」
はどうでしょう？

「わざわざ」ってつけると迷惑だったと思われるんですね。
そういう感覚は無かったです。

なんでしょうね？
他の手段もある（もしくはやらないという選択もある）のだけど、
時間や労力を使ってやってくれた時などに言ってしまう気がします。
うまく表現できないけど。普通のありがとうにプラスして言っちゃう。
迷惑ということは全然なくて、純粋にありがとうの気持ちなんですが。
やってもらって申し訳ない気持ちがある時に言っているのかなあ。

迷惑に思っている時にも使うんですね。
勉強になりました。

言葉を曲解しているだけです。

「お手間を取らせて申し訳ありません。」という意味にとれば，「もしかして迷惑だったかな？」などとはならないと思います。

「わざわざお越しいただきまして」や「わざわざお電話いただきまして」は、「ご足労いただきまして」や「お手数おかけしまして」と同じ意味だと思います。相手の労をねぎらっているだけです。こちらからすべきところを自らしていただいたというような意味だと思います。「やらなくてもいいことをやってくれた」と受け取ると聞くと、「してくださった」というへりくだりの気持ちがわからないんだなと感じます。
「わざわざ」を否定的に感じるという意見は、そう思わない人間には「お疲れ様でした」や「お暑い中をお越しいただきまして」などの言葉は素直に聞けるのか？と不思議になったりします。

主人が「わざわざ」を多用する人です。たぶん、感謝の意を強調するために使っているのだと思うのですが、私もトピ主様同様違和感を感じています。

ご丁寧にありがとうございます。
遠いところお越しいただいてありがとうございます。
お忙しい中お電話いただき、ありがとうございます。

などその時々で言葉を換えればいいと思います。
それをすべて「わざわざ」で表現する語彙力のなさ、手抜き感が嫌いなのかも・・・と今気づきました。

皆さんおそらく適当な言葉が見つからず、「わざわざ」という言い方になるのだと思います。
私は「わざわざ」ではなく「ご丁寧に」を使ってます。

たしも、
ワザワザ
は下手したらイヤミになると思ってました。

目上の方には、
わざわざこんな事までしてくださったんですか？ありがとうございます！
みたいに、感謝の表現で使って、
わざわざしていただかなくても良かったのに…すみません、ありがとうございました。
みたいに、否定的な感じでは使わない様にしていました。

同じ使い回しは、
大変だったのではないですか？
程度しか思い付かないので、私も他の方のレスを参考にさせて頂きたいです。

『全然大丈夫！』
『全然気にしないで！』
『全然おいしい！』

『全然』も今は普通に使っていますが、昔は否定の意味合いが強かった気がします。
『わざわざ』と似てますよね。

前後の文章次第で、嫌味っぽい感じは消えそうな気がします。
『足元のお悪い中、わざわざお越しいただいてありがとうございます』
『お忙しい最中、わざわざ時間をさいて頂きありがとうございます』

う～ん、それでもまだ嫌味っぽいかなぁ。

言葉は時代によって流行り・廃りがあるからむずかしいですね。

私も、わざわざ…と書こうとして、あれ？と思った事があります。
そのかわりに「ご丁寧に…」と、付けても、「わざわざ」と同じように受け取られたらわるいなと思い、結局、何も付けず、「ご連絡ありがとうございました」としました。

言葉は時代と共に変わるというのをＴＶで見ました。
なので「わざわざ」も変化して行くのかもしれませんが、改めて「わざわざ」を考え直してみると難しい言葉ですね。

「わざわざ遠回りした」は近道の方法があったが理由があり遠回りをした。
「わざわざ車で来た」は他の方法もあったが　自動車の必要性を感じ自動車を選んだ。
この場合の「わざわざ」は選択肢の中から　困難または、貴重な選択をした時に使ってます。

「わざわざお越しいただいて」「わざわざお電話いただいて」に続く言葉は
「ありがとうございます」や「恐縮です」という感じですよね。
この「わざわざ」は相手の行為に感謝している時に使っています。

「わざわざ電話しないで」や「わざわざ見ないで」など「わざわざ＋否定」はいっそう否定を強める形になるので　目上の人にはちょっと失礼ですね。
「わざわざ～しなくても」という言い方は目下か同等の相手には使うと思います。

混乱して来ました・・・トピ主さんは「わざわざ＋は否定形」が先行してしまうようですが「肯定的なわざわざ」の使い方を覚えれば違和感は無くなると思われます。