I hate to resurrect an old thread, but this is a very important issue for me. I'm a US citizen married to a Taiwan citizen in the United States. We have a marriage license/certificate in the US. As far as I know from the AIT website, all we need to do to get over this catch-22 is not try to get married in Taiwan, but get the US marriage recognized in Taiwan. You can do this by writing an affidavit stating the certificate is legitimate and that's it. You can then get a JFRV.
It sounds pretty simple and straightforward to do.... has anyone else's experience been different? Guess it's different for different countries??