You said in a comment that you were referring to the material conditional, not other notions of if/then like the antecedent being a cause of the consequent, or the antecedent logically implying the consequent. So let's get rid of the if/then structure and write them explicitly as material conditionals:
A) "I stay" -> "I eat fish"
B) "I didn't stay" -> "I eat fish"
You are worried about the possibility that both A) and B) are true simultaneously, and we apply modus tollens to each one in turn to get two more true statements:
C) "I didn't eat fish" -> "I didn't stay"
D) "I didn't eat fish" -> "I stay"
It is indeed possible that A) "I stay" -> "I eat fish" and B) "I didn't stay" -> "I eat fish" are simultaneously true--the material conditional is defined by its truth table, and the truth table indicates that as long as the consequent is true, the material conditional is true regardless of whether the antecedent is true. So in the case where "I eat fish" is true, both your first two material conditionals A) and B) are automatically true. And if "I eat fish" is true, there's no problem with modus tollens, since both C) "I didn't eat fish" -> "I didn't stay" and D) "I didn't eat fish" -> "I stay" involve a false antecedent in this case, and the truth table for the material conditional shows that it's always true when the antecedent is false, regardless of whether the consequent is true or false.
To put it another way, if you learn that C) "I didn't eat fish" -> "I didn't stay" is true but the antecedent "I didn't eat fish" is false, then you can't deduce anything about whether "I didn't stay" is true or false. Likewise if you learn D) "I didn't eat fish" -> "I stay" is true but "I didn't eat fish" is false, again you can deduce nothing about whether "I stay" is true or false. So as long as "I didn't eat fish" is false, learning that both of your second two statements C) and D) are true doesn't lead to any contradictory deductions about whether you stayed or didn't stay.
On the other hand, let's consider the other case where "I eat fish" is false/"I didn't eat fish" is true. In the case that the consequent is false, the truth table shows it is not possible that both A) "I stay" -> "I eat fish" and B) "I didn't stay" -> "I eat fish" are simultaneously true. When the consequent is false, the material conditional is true if the antecedent is false as well, but the material conditional is false if the antecedent is true.
So, if "I eat fish" is false, there are now two different possibilities:
1) If "I stay" is false as well, then A) "I stay" -> "I eat fish" is true (both antecedent and consequent are false) but B) "I didn't stay" -> "I eat fish" is false (antecedent is true but consequent is false).
2) If "I stay" is true, then A) "I stay" -> "I eat fish" is false (antecedent is true but consequent is false) while B) "I didn't stay" -> "I eat fish" is true (antecedent and consequent both false).
The main point to note here is that under any circumstances where "I eat fish" is false (or equivalently 'I didn't eat fish' is true), only one of your original two statements A) and B) can be true while the other must be false, which implies only one of the two derived statements C) and D) can be true while other must be false as well. Whereas your paradox arose from assuming both of the first pair A) and B) were true and then applying modus tollens to both to get two more true statements C) and D) that both had the antecedent "I didn't eat fish", and finding that these two statements led to inconsistent conclusions about whether you stayed. But what I've shown above is that C) and D) can only both be true if their antecedent "I didn't eat fish" is false, in which case nothing can be deduced from them about whether you stayed, whereas if "I didn't eat fish" is true than only one of C) or D) can be true. Either way, there's no contradiction.
if
" meaning "if and only if" (sometimes written as "iff
"), where these two statements would indeed be contradictory. But in formal logic, "if
" is only a one-directional implication.