はじめに
Movable Typeを使用するのに良い感じなレンタルサーバーの一覧です。
以下のような条件で探して見つけたレンタルサーバーの比較になります。
・MySQL必須
・転送量無制限もしくは30GB/月程度
・telnet or sshが使用可能
・PHPでmbstringが使用可能
・5,000円/月に収まること
実際に使用したものはそのサービスの使用感について書いていますが、使用していないものについては勝手に感じた事を書いているに過ぎません。
また、以下にあげたレンタルサーバーであれば必ずMovable Typeを設置できるというわけでもありませんのでご注意ください。

個人的にオススメかもと感じたレンタルサーバーは背景色を変えてみました。
ちなみに、所々にアフィリエイトが埋め込んであります。

ステータスの説明
試…試用済み
問…問い合わせ済み
検…検討のみ
名称
(コース)
ステータス 印象 月額 容量 転送量 telnet/ssh Perl Image::Magick Jcode PHP mbstring MySQL その他
ロリポップ 容量が多少不安だけれどもオススメ!Movable Typeの動作には定評有り 250円 200MB 無し × 5.8.0 4.2.2 Ruby
さくらレンタルサーバー
(スタンダード)
文句なしでオススメ 500円 300MB 無し telnet/ssh 5.8.x 4.x Ruby、Python
ハッスルサーバー 容量も値段も文句なし。あとはサイトとかコントロールパネルとかが洗練されると信頼性が増すのだけれど。 208円 500MB 無し × 5.8.x 4.3.8 4.0.22
EUC
Ruby、Python
デジパワー
(ドラゴン)
サーバーがかなり重いけど、それ以外は文句無し
超多機能
1375円 無制限 無し ssh 5.6.1 4.3.4 4.0.15
EUC

XREA 快適だしコストパフォーマンスも高いけれど、だがたまにCGIの実行エラーが出るのが難点 200円 300MB 30GB ssh 5.6.1 4.3.4 3.23.58
EUC
Ruby
zerokara.com
(P)
サーバーが重い、値段が高い、ただし信頼性は高い(と思う) 5400円 450MB 24GB telnet/ssh 5.005_03 × 4.3.2 3.23.58
Latin-1
Python
ウィルネット
(Linux-500)
なんとなく好印象
値段が値段だけに信頼性も高いかも
オススメか
4000円 500MB 30GB ssh 5.6.1 4.3.0 4.0.14
EUC

Xserver
(X10)
なんとなく好印象
良さそう
1200円 300MB 無し 5.8.1 4.3.3 4.0.15
Latin-1

WADAX
(ブロンズ)
問い合わせをしたけれど返事がない
容量が不安
2200円 150MB 無し ssh 5.x 4.x sshオプション
kagoya Internet Routing
(40)
転送量が不安
問い合わせには迅速に返答あり
4000円 400MB 12GB × 5.005_03 4.3.1 3.23.49
EUC
MySQLオプション
A&Sコミュニケイションズ
(B)
Image::Magick使用不可、それ以外は文句が無い
惜しい
4000円 300MB 30GB ssh 5.6.1 × 4.3.3 4.0.15
EUC

エクセレント
(スタンダード)
良さそうだけれど実際に使用してみると重かったりするのかも 3500円 300MB 無し ssh 5.6.0 4.x 3.23
EUC
Servlet/JSP
セキュリティネット
(スタンダード)
MySQL使用不可なので問題外 4900円 500MB 無し × 5.6.0 × × 4.0.6 × ×
1stレンタルサーバー
(ビジネス)
問い合わせたけれど返事が遅かった 3600円 700MB 無し × 4.2.2 × 3.23.54
EUC
Servlet/JSP,mod_perl
RAMALL
(エコノミー)
問い合わせたけれど返事がありません 1200円 300MB 無し 5.6.0 4.x Servlet/JSP,mod_perl
ワイワイホスティング
(プラチナ)
サポートがアホすぎて話にならない 3500円 350MB 75GB x 5.008 4.3.2 4.0.14
EUC
ウィルススキャン
ワイアイウェブ
(プロ)
サポートが使えないっぽい 3980円 500MB 5.8.x 4.3.3 JSP,Ruby,mod_perl
アヴァンス
(スタンダード)
容量が不安、でもサイトの作りは好感が持てる 2500円 200MB telnet/ssh 5.6.1 4.x メールアドレス無制限
シフトウェブ サブドメイン無しでのアクセスが不可
そこにこだわらなければ使えそう
1000円 300MB 18GB x? 5.x 4.3.1 4.0.12 Ruby
ASJ
(アドバンス)
転送量が少なすぎ 4500円 100MB 8GB ssh 5.x 4.x
EUC
Ruby
HOSTMYCGI
(p++)
転送量が少々足りない
それ以外はいいんだけどなー
4950円 375MB 20GB × 5.8.0 4.3.2 4.0.15
スピーバー
(Speever4)
値段の割にサービスが物足りない感じ 5000円 300MB 無し telnet/ssh 5.0x 4.2.3 3.23.53
80code
(Suite)
転送量が不安 1920円 500MB 25GB ssh 5.8.0 4.3.3 Ruby
COMAX
(ビジネス)
値段が高い 6300円 300MB 45GB × 5.x 4.3.2 3.23.49
EUC

MAILYWEB
(スモール)
値段が高い 6980円 1GB 無し telnet/ssh 5.8.0 4.2.2 3.23.54 Ruby,eRuby,etc.
SPPD
(パワフル)
MySQLを使用すると予算オーバー 4800円 200MB 無し telnet/ssh 5.6.1 4.3.4 3.27.49以上 Ruby,MySQLオプション
使えるネット
(エンシム転売)
対応が悪いらしい 5000円 10GB 50GB ssh
Joe's Web Hosting
(共用サーバー)
とにかくネット上での評判が悪すぎ 3000円 無制限 無し ssh 5.6.1 4.3.4 4.0.15
AKIRA
(エコノミー)
転送量が足りない 3000円 300MB 8GB ssh 5.005_03 4.3.3 4.0.14 Servlet/JSP,Web_DAV
ROCKET3 Win系サーバだから問題外 5.x 4.x × ASP/ASP.NET,ウィルススキャン
ルビーネット
(WP05)
転送量が足りない 4250円 1GB 15GB 5.6.1 4.3.2 4.1.2 Ruby
Cyberjellyfish
(プレミアム)
ドル払いが嫌い 20$ 250MB 無し 4.x MySQLオプション
mixedmedia
(プロフェッショナル)
MySQL使用不可なので問題外 4150円 1GB × ×
site5
(VANTAGE)
海外は不安 14.95$ 200MB 1GB ssh 5.x 4.1.0 ×
Latin-1
Servlet,Python
ASJホスティングサービス
(アドバンス)
容量が足りない 3800円 100MB 8GB ssh 5.x 4.x Ruby
inetd
(Power)
MySQL使用不可(PostgreSQLは可) 2980円 200MB 無し telnet/ssh jperl5 4.x × Ruby
むぎわら 転送量が足りない 2850円 600MB 15GB ssh 5.x 4.x Python