※こちらが間違えている場合もあるので、必ずご自身で各サイトの規約を確認してください。

ツイートや動画内に曲名を書いているのは権利関係をクリアするためではなく元ネタを視聴者に教えてるだけです。

規約関係をクリアした上でMADを作るのは本来はかなり難しいです。
ただskyは運営の規約で非営利かつ投稿先のルールを遵守すればOK、またボカロも曲によって規約が異なることもありますが二次使用が比較的簡単なので、投稿先を選べば全部クリアすることもできます。

死ぬほど長文になるのでざっくりとしか書きませんがTwitterはJASRACと包括契約を結んでいないので、ボカロ曲がJASRACに権利を委託している場合規約に引っかかります。
包括契約を結んでいる代表的なサイトはニコニコとYou Tubeです。ただし原曲そのままを利用することはできません(作者が許可している場合を除く)。

例えば歌ってみたで言うとCDの声だけ消して演奏に自分の声を載せて投稿するのはNG、演奏も自分でして歌うのはOKです。
なので演奏も歌も自信がない場合は許可を出している投稿主さんからお借りして動画を作るという手もあります。
ニコニコの場合はニコニ・コモンズというシステムがあるので規約を把握しやすいしお借りしやすいです。

規約関係をクリアした上で原曲そのものを使いたい場合はどうするかというと、現状ニコニコに投稿するのが一番です。
例えばボカロPがニコニコ動画に原曲を投稿していて子作品を作ってもいいと許可していた場合はそれを使えるし、ニコニコは一部のCDと原曲そのまま使っていいよ！という契約を結んでいます。
このあたりはニコニ・コモンズ、コンテンツツリーの規約を読んでください。
原曲が使えるCDはニコニコがリストを作っているの必ずそちらを確認してください。利用された許諾原盤ランキングというのもあります。

ですので、現状権利関係をクリアするとなるとニコニコに投稿してTwitterでリンクを貼って見てもらうのが一番楽です。
曲によってはJASRACに委託しないで個人で管理している場合もあるので必ずしもとは言えないです(これに関してはJASRACのサイトで登録されているか確認できます)。
とりあえずニコニコ、JASRACの規約を見るのをおすすめします。