I have not yet written your letter?
That should be accepted. Personally, I'd put "yet" at the end of the sentence, but yours is also perfect. Make a report if you get it again.
What's wrong with "I have still not written..."?
Nothing. That's what I put.