どのように扱うかにもよりますが､重要なのはﾃﾞｨｽｸ容量ではなくﾒﾓﾘ容量だと思います｡
さくらVPSの1000円ﾌﾟﾗﾝだとおそらく2GB程度の容量しか使えないと思うので､ﾃﾞｰﾀﾍﾞｰｽの構造にもよりますが､4GBのﾌﾟﾗﾝにしてはどうでしょうか｡
後はSQL文を効果的に機能させるためにさまざまなｿｰﾄ用のｶﾗﾑを作るなど､工夫をすれば十分に早いｿｰﾄが可能だと思います｡

私は2300万件､20ｶﾗﾑのﾃﾞｰﾀを4GBのVPSｻｰﾊﾞで動かしていますが､快適に使用できます｡

ﾄﾗﾝｻﾞｸｼｮﾝは｢1日5000件ほどのINSERT｣だけですか？
それであれば｢さくらのVPSの1000円くらいのﾌﾟﾗﾝ｣で十分です｡

もしそのDBをﾈｯﾄ公開するのであれば､同時接続数を制限しつつsnmpdで負荷監視を行って､徐々に接続数を増やしていくといいと思います｡

一応､ｼｽﾃﾑ屋さんです｡
止まっちゃいけないｼｽﾃﾑを扱うことが多いので､ちょっと気にし過ぎかもしれませんが､気になることは幾つもあります｡

• insert 以外 (update, delete, select) の呼量
• ﾃｰﾌﾞﾙの設計 (特に､ｲﾝﾃﾞｯｸｽ)
• 想定している同時接続数
• DB をｱｸｾｽするｱﾌﾟﾘの機能
• 使えるﾒﾓﾘ
• CPU の性能

それぞれ､互いに絡んでくるので､質問で挙げられている程度の情報だと､それぞれの項目について個別にどうこう､ということが言いにくいです｡

まず気になったのは呼量です｡
ﾃﾞｰﾀを入れっぱなし､ということは無いですよね｡
ｲﾝﾀｰﾈｯﾄに接続されているｻｰﾊﾞを使うということは､検索前提だと思います｡
ｲﾝﾃﾞｯｸｽをどう張るかで､性能は全然変わります｡
やたらに張れば良いというわけではなく､意味も無く増やすと､ｲﾝﾃﾞｯｸｽもﾃﾞｨｽｸを使いますし､更新系の操作の負荷を増やすことにつながります｡
CPU の負荷が増えるということは､CPU の性能が大事になります｡

多少､ｲﾝﾃﾞｯｸｽの張り方が悪くても､ﾒﾓﾘをじゃぶじゃぶ使って､DB のﾊﾞｯﾌｧを増やしたり､ｱｸｾｽするｱﾌﾟﾘのｷｬｯｼｭ機能 (PHP だったら memcached のような) を使うことで､性能の改善はできます｡
但し､利用できるﾒﾓﾘがあれば､です｡

ﾃｰﾌﾞﾙの構造が単純で､ｱﾌﾟﾘもあまり凝ってなくて､単発の性能は問題が無くても､同時に何人使用する(という想定)か､というのも重要です｡
Apache や MySQL の同時接続数を増やすしかありませんが､当然､ﾒﾓﾘは必要になります｡
多重度を増やして､大量の処理をさばくということになれば､CPU に要求される性能は高いものになり案素｡

VPS を想定しているのであれば､物理的なﾎｽﾄのﾘｿｰｽを複数で分け合うわけですから､CPU ﾀｲﾑやﾒﾓﾘの使用量に対する制限が出てくることも想定されます｡


後､ちょっと気になってるのは､

さほど気にせずずっと動くものでしょうか｡

1000万ﾚｺｰﾄﾞで､5000件/日の insert だと､単純に割り算をすると五年半くらいということになります｡
｢ずっと｣というには､ぼくの感覚としてはちょっと短いかな､という気もしますが､通常のｼｽﾃﾑであればﾊｰﾄﾞのﾘﾌﾟﾚｰｽを行うくらいの期間なので､ﾚﾝﾀﾙｻｰﾊﾞなら借り換えてるよ､ということでしょうか｡