We didn't fight recently .
We haven't fought recently.
Personally, the second sentence sounds more natural to me than the first one does -- and I am very definitely a speaker of American English.
In a negative simple past tense construction, something like this seems more natural to me:
- I didn't know until recently that he'd been fired.
However, I'd like to mention that I cannot recall ever having seen any reputable grammar book that prohibited the use of "recently" with the simple past tense. As far as I'm concerned, that idea is simply a misunderstanding or misinterpretation of the fact that the word "recently" is used very often with the present perfect. "Very often" should not be interpreted as meaning "exclusively". Thus, the following sentence is perfectly grammatical in both BE and in AmE:
- The new Marquess of Bath, who recently inherited
the vast Longleat estate, was on holiday with his family in France.
(That sentence was in fact taken from a British publication.)
Generally speaking, you can use the past simple together with the word "recently" to refer to a specific past event that took place at a "recent time" (i.e. "not long ago").