現在、カナダ国内より国外申請の準備をしている者です。

オンタリオ州でMarriage Certificateを取得するには3〜4ヶ月ほど時間を要しますが、イミグレに何度か聞いたところMarriage Licenseではダメ！Marriage Certificateを出してくださいと言われているので待つしかないとは思っているのですが、それでも時間がかかり過ぎるので何か早い方法がないかなと考えています。
例えばMarriage Licenseを先に提出しメモか何かで後日Marriage Licenseを提出します…などといった形で申請された方はいらっしゃいますか？

マリッジライセンスとマリッジサーティフィケイトとはまったく違うものですよ。
マリッジライセンスは、「結婚をすることを許可」するもので、このライセンスが発行されてから３ヶ月以内に結婚しなければいけません。
そして結婚した後に、「結婚したことを証明」するものがマリッジサーティフィケイトです。
なのでイミグレの方が言うように、マリッジライセンスを提出しても送り返されてしまうと思いますよ。
　

Milkさん、ありがとうございます。
そうですね！辛抱強くMarriage Certificateを待つ事にいたします。
　

私はトピ主さんの方法で大丈夫でした。
先にライセンスを送り、メモを付けました。
後日、追加送付した時、オンラインで追加書類受け取りましたと
表示も出てました。
係官にもよると思うので、１００％大丈夫ですとは言えないとは思いますが・・ 　

トピ主さんがもう健康診断も受診していて、あとはMarriage Certificate待ちというのなら、後送する旨のメモをつけて申請してしまうことも可能は可能です。あまりお勧めしませんが、たいていの書類は後送できます。

Marriage Licenseは結婚の証明になりませんので（Licenseを買って結婚しないこともありますから）、添付してもあまり意味はないと思います。むしろ、結婚式のときに小さな証明書をもらえると聞いているのですが、それがあればそちらを添付した方がいいでしょう。以前はそれだけで申請できたのですが、最近は正式なMarriage Certificateを要求されることが多いようです。

トピ主さんがまだ健康診断を受診しておらず、申請書も準備できていないようなら、いずれにしても健康診断の結果が出るのに2〜3ヶ月かかりますから、全部そろえて送った方がいいと思います。その方が紛失の心配もありませんし。

Res.1 Milkさんの別トピでの情報ですが、
＞オンタリオ州でも、急ぎであれはマリッジサーティフィケートをピ
＞ックアップする事が出来ます。
＞ちなみにオンタリオ州では、結婚してからきちんとレジスターされ
＞るまで約２ヶ月かかるということなので、それからサーティフィケ
＞イトが発行される流れになっていうとのことです。
http://bbs.jpcanada.com/topic_dtl.php?bbs=5&msgid=3482&resid=9&ntopic=1&cat=0

とのことです。ひょっとして4ヶ月はかからないかも、と思うのですが。 　

けいさんの仰る「結婚式の時にもらえる小さな証明書」と言うのはライセンスの半ピラですね。ライセンスに式当日、本人達とコミッショナー、証人二人がライセンスの切り取れる部分にサインします。それを貰って通常婚姻関係の証明（コミッショナー認証の物）とされるのですが、移民局などはもっと正式な書類（政府認証の物）が求められますね。因みに政府発行の書類にも2種類あって、私が移民局に電話して確認した時には長い（高い方、＄22だった様な…）方の書類が必要、との事でした。

私は国内申請で、この間面接に行ったのですが、その時まだMarriage Certificate待ちの状態でした。が、レシートとライセンスの半ピラを持って行ったら問題無くステイタス（コモンロー→婚姻関係）を変更してもらえました。因みにMarriage Certificateを申請したのは10月半ばです。式は9月の半ばでした。

後送するならライセンスのレシートも一緒に付けると良いと思います。でも他の方も仰る通り待てるなら待って全部一緒に送った方が確実でしょうね。