From a fabricator erector standpoint, we typically use E309 as the filler metal of choice, but the filler metal does not appear the primary source of your situation.
From what you have said, it sounds as though the problem was in the procedure (or lack thereof). You did not mention the thickness of the materials, but the fact that your getting consistant failure indicates that the rebar was not the A706, and that preheat was not being done. If a welding procedure was submitted and distructive test performed with satisfactory results to gain it's approval, then the procedure was not followed.
Fabricating companies are production driven and welding carbon to stainless is a more sensitive procedure that should be avoided in structurally critical conditions. There are a variety of companies that produce weld studs and derformed bar in stainless steel materials that can be welded with consistantly sound results. The materials are expensive, but not as expensive as the forensic studies and consequencial repairs to carbon/stainless joints.