>対応している可能性もありそうなので、Connector/Neの違うバージョンをインストールしてみます。
調べてからインストールするか、知っている人に聞くなどした方がいいと思いますよ。

>直接プログラムでかけばConnector/Neやデータベースエクスプローラーは関係なくデータの更新などができるのでしょうか？
できますよ。
でも最初に書いたように私は経験がないので具体的な方法は別に調べて方がいいと思います。
Googleで検索するとプログラム例のあるサイトもヒットします。
http://www.google.co.jp/search?hl=ja&safe=off&q=VB+MySQL+%E6%8E%A5%E7%B6%9A%E3%80%80-%226.0%22&aq=f&aqi=&aql=&oq=&gs_rfai=

ただし、繰り返しになりますが、MySQL側に到達できないファイアーウォールの問題とFC2の設定の問題が解決できないと何をやってもつながらないです。
たいて、データベースエクスプローラで接続できない場合は何か問題があるので、プログラムしてもダメなケースが多いです。
私が言いたかったのは「データベースエクスプローラで接続できなければ、プログラムで接続できないわけではない」ということです。

>もし許可していない場合は他のサーバーと契約をしたほうがよいのでしょうか？
FC2とゴドーさんがどのような目的でどのようなサービスを契約したかわからないことと、私はFC2が提供しているサービスの内容についてまったく知らないことをまずご理解ください。

一般論を話しています。
一般論ではデータベースへのリモート接続を許可するかしないかは管理者次第です。レンタルDB(というのかわかりませんが)の場合でも事情は同じです。リモート接続を許可するかしないかは重要なことなので明記してあるのではないかと思います。

リモート接続を許可しないレンタルDB(?)の使い道は、プログラムとセットで考えて、プログラムをDB側のサーバーにアップロードして接続することです。
こうすると、そのプログラムから見ればデータベースがローカルにあるので接続できます。
ほとんどの場合そのプログラムはphpやASP.NET, javaなどのプログラムで、ユーザーはそのプログラムにWebブラウザからURLを使ってアクセスし、そのプログラムが裏でデータベースに接続する形になります。
この掲示板もマイクロソフトのSQL Azureというレンタル的なデータベースを利用しており、プログラム自体もマイクロソフトのサーバーにアップロードしています。(プログラムは私が作っています。なお、SQL Azureの場合はリモート接続も可能です。)

ですので、ゴドーさんがこのサービスを利用し続けるか、他のサービスを探すかは
１．ゴドーさんは何をやりたいのか
２．ゴドーさんが契約しているFC2のサービスの内容は何か
の２点を考えて決める必要があり、ゴドーさんのやりたいことがFC2で実現できないのであれば別のサービスを探したほうがいいとは思いますが、現時点で私は１も２もわからない状況なのでなんとも言えません。

１がわからないので、たとえば、自分で作成したプログラムのデータ保存場所としてMySQLを利用したいということと仮定すると
アドバイスとしては、
①まず、データベースエクスプローラを使ってゴドーさんのローカルのMySQLに接続する方法を模索。
②それができたら、次に、FC2側のMySQLに接続する方法を模索。
③それができなければ、プログラム自体をFC2側にアップロードすることの可否を調べる。
④それが可であれば、プログラムを作成しアップロードする
という流れになるのかと思います。

難易度としてはプロのプログラマーでも経験１、２年レベルの人には厳しいかもしれないレベルかなと思います。

よかったら、１のゴドーさんがやりたいことを教えてください。
ひょっとするともっといい方法があるかもしれません。