Mac OS X 10.6.7 の Firefox 4.0.1でサンプルのサイトを見てみました。
お書きのように、初回アクセス時には音が鳴りますが、再読み込みや新規タブ等で開いた場合は再生されませんね。
さらに、件のサイトでは「 QuickTime をインストールしろと」云うダイアログが出てきました（無視しましたけど)
これ、Windows 環境の Firefox では再現しないのでしょうか？
で、通常のリロードでは音は再生されませんが、スーパーリロード（command + shift + R か command + shift を押しながら読み込みボタンをクリック）で読込み直すか、Cache をクリアすれば再読み込みでも再生されます。
ちなみに、先のページに埋め込まれている midi ファイルは、Firefox で直接開いても再生できませんでした。（Safari 5.0.5 では両方ともできます）
これ、 pluto.dti.ne.jp のキャッシュをブロックしてやれば良いようですが、そういったアドオンや設定も見つけられませんでした。
ということで、スーパーリロードか Cache をクリアする方法で対処しなければならないようです。
Bugzila@mozilla ではそのものずばりの報告は上がっていないようですが、midi が再生できない問題に対し、クロスブラウザ対応に向け、本家 MozillaZine の Background music does not play にある、Webpage authors を参考にするようにというコメントがありました。
ご自身のサイトでの問題には、上記や HTMLタグ/埋め込みタグ/様々な形式のデータを埋め込む - TAG index Webサイト を参考にされてはどうでしょうか。