Thanks for raising this. I think this should be addressed now.
This was my fault. You are right that, normally, downvoted questions can't be deleted if they have an upvoted answer. Here's what happened. Yesterday I dealt with a sockpuppet ring. This triggers automatic deletion of all questions with a vote score below 0 from the socks. I manually reviewed all such deletions to make sure we weren't losing good questions, and rescued some of them. There were three remaining questions that I judged weren't worth keeping because the questions were so specific that I doubted anyone would ever have the same question again. So, I left them deleted.
However, after looking at this again, you raise a good point; for at least two of those questions, the answers do seem like they have lasting value. I made the wrong call. Sorry about that.
So, here's what I've done to save the good material. For two of those three questions, I did radical surgery on the question to get at the conceptual point that the answer is addressing, and I've undeleted those two questions. Hopefully now they are decent questions that someone might plausibly have again in the future, and that they'll be able to find if so. You can look at Detect whether one Turing machine invokes another and Solving diophantine equations -- does having a bound on the size of the solution help? if you want to review the surgery I did and make further improvements.
There is one remaining question that I just don't see value in. It's a "please give me feedback on my idea" question that had lots of symbols but doesn't seem to have any useful content that I could extract, and the answer basically says that. I don't see much chance that this will be useful to anyone else in the future. Perhaps you'll see a way to extract a useful interesting question that has a non-trivial answer, and if so great, but I couldn't. So, I'm going to leave this deleted. (Caveat: I suspect this link will only be accessible if you have at least 10K reputation, so you might not be able to see the deleted question.)
I hope this sounds like a reasonable resolution. Thanks for the nudge about this; I'm happier now that we could find a way to save the useful content that you and others wrote.