Lucky it wasn't a certain registrar I know of where the grace period is -1 days.
Anyways, I would think that the registrar having billed you has sent you concrete proof that you auto-renewed. Especially since you did not in any way dispute the charge, nor did they credit the amount back.
Therefore, it is up to the registrar to retrieve the domain. A stiffly worded registered letter is called for. Send an electronic copy if you want of course, but make sure you also refer to the hardcopy. You don't want any of that "we never got the email" nonsense.