Sounds to me as if you are asking them the wrong question.
Of course you can get married -- either in the US or in Taiwan -- without a criminal history check.
However, if you want to obtain a Taiwan visa based on your married status, you WILL require the check.
Are you asking them if you can get married without the check, or are you asking them if you can get a Joining Family Resident Visa without the check?
The requirements are different.