"Believe again" is actually not very well translated. re- chiefly has the meaning of "back" (cf. retro), so "take back one's pledge" does indeed seem accurate. The "again" here is sloppiness on the editor's part.
Let me draw your attention to the Oxford Latin Dictionary's definition of re-:
re-, prefix....Vbl. prefix denoting movement back or in reverse (redeo, reuerto, reuoco), withdrawal (recondo, religo, reticeo), reversal of a previous process (refrigero, resoluo, retego), restoration (renouo, reualesco), response or opposition (rebello, redarguo, respondeo), separation (remoueo), repeated action (repeto, repleo).
Of the examples given, movement indicating 'back' in some way encompass the first three types of use, while "again" is rather limited.
It also helps to remember that credere takes a dative, and therefore has a sense of giving implicit in it. Credere in fact was originally tied to giving credit, and trust naturally stems from there. Likewise, the Latin, Greek, and Hebrew words for "belief" all refer to 'trust' and 'loyalty (fides is the other Latin word for belief in god, and the English derivative fidelity still maintain the sense of 'loyalty').
As far as recroire, if we imagine the opposite (ie: recroire without the prefix; croire) to mean not just belief, but "believing in oneself", then to add the prefix to it would give us the meaning of "taking back belief in oneself" or "no longer believing in oneself". If you no longer trust yourself in battle, the option is to retreat or, if you're honorable, surrender.