The Chavos Da'as (Y.D. siman beg. of siman 110) has an interesting spin on the Rambam's opinion that sfeika d'orasya l'chumra is just a din derabbanan. Chavos Da'as explains that the reason why m'doraysa it is permitted to eat safeik neveilah or safeik cheilev or enagage in any safeik issur is because the term "neveilah" means that which is vaday neveilah, the term "cheilev" means vaday cheilev, etc. with respect to all other issurim. That being the case, the flipside also must be true: even the Rambam would agree that if one ate matzah which is safeik baked properly or not, one is not yotzei the mitzvah -- the term "matzah" means vaday matzah, to the exclusion of a safeik kiyum hamitzvah, and the same would be true with respect to all other cases of kiyum hamitzvah.
This approach resolves a number of questions raised on the Rambam. For example, the gemara (R"H 13) discusses how Bnei Yisrael offered the korban ha'omer when they first entered Eretz Yisrael. How did they obtain wheat which would satisfy the requirement of "bkutzrichem", wheat grown and harvested by Jews, when the Jewish people crossed the Jordan just days before the korban had to be brought? The gemara answers that they used wheat which had grown less than 1/3 under non-Jewish ownership and then ripened under Jewish ownership in those few intervening days. Asks the gemara, but how could they tell the difference if the wheat was already 1/3 grown yet or not -- there was still a chance that the wheat they harvested was not acceptable!?
If sfeika d'oraysa is permitted under all circumstances, then what is the gemara's question -- true, there was a chance that the wheat was not acceptable, but md'oraysa we don't need to be concerned about a safeik!
Based on the analysis of the Chavos Da'as the gemara makes perfect sense. Only a safeik issur is permitted min haTorah according to the Rambam, but even the Rambam would agree that a kiyum mitzvah can be fulfilled only if done in a way that fulfills the Torah's criteria with certainty.