1. Empirical or natural doubts.
We have some evidence that P, but is it enough evidence? To feel confident in claiming that P, we need to pass a threshold of evidence, T. In a natural doubt, our evidence for P is less than T. Therefore, while we may suspect P, we still feel doubt. This sort of doubt is very common in daily life, and is in theory easily fixed: just go and find more evidence, until the evidence passes the threshold (or until it passes the opposite threshold, -T, and we're confident that P is false).
Here, you're right, we could draw finer distinctions. I'd suggest maybe three kinds of empirical doubt, following your lines: doubts where we can find more evidence; doubts where we can't in practice find the evidence but we do know what evidence we'd be looking for and how to find it; and doubts where we're not even sure where to look for the evidence, or what the evidence might look like. But these are all empirical doubts - they're all requests for more information.
2. Conflict doubts
In an empirical doubt, we doubt P, because we don't believe our evidence has passed the threshold, T, that would let us feel sure of P's truth. We need more information. But not all doubts require more information. If I ask "is a tomato a vegetable?", and you say "I'm not sure", you're not really saying you need more information. Maybe you do, but maybe you have all the information and still aren't sure what answer to give. If I ask "if you play chess on a 7x7 board with no queen, is it still chess?" and you're not sure of the answer, that doesn't mean you think you need to research the history or sociology of chess a little more. You could have all the relevant knowledge in the world and still not know. Your problem here is not that you don't have ENOUGH evidence, but that your evidence is CONFLICTING. One thing makes you want to say 'yes', another makes you want to say 'no'. It's not that the evidence doesn't pass T... it's that you can't decide whether it passes T or not. You can't just take the evidence for, and subtract the evidence against, because you're not sure how to weight different reasons or signs against one another. This sort of doubt often arises around definitions, and also around actions - it's the sort of doubt people often feel about whether they're doing the right (morally or pragmatically) thing. This sort of doubt is often resolved through making a decision (or having one made for you), and often by narrowing the focus and answering only with relevance to a specific topic or time (like "for the purposes of deciding what to put in this fruit salad, let's say that tomato is NOT a fruit...")
3. Anxiety doubts
With empirical doubts, we don't have enough evidence that P. With conflict doubts, we may have plenty of evidence that P, but we also seem to have incommensurable evidence that NOT P. Sometimes, though, we have masses of evidence that P, and no evidence that not P... and still feel doubt. We check five times to make sure that the gas isn't on... but are we sure? What if you're misremembering those checks, and weren't really concentrating? Maybe if you check a sixth time you'll realise the gas was on all along? This sort of doubt arises because we know that, however overwhelming the evidence we have is, because there's an infinite amount of possible information we haven't yet acquired, it's always possible that the facts we don't know yet would outweigh the evidence we have. That is to say, when we consider the infinite information in the world, and our paltry stock of known facts, we find it hard to justify placing T at any finite point. No matter how high we set the threshold, even if we meet it we can still fear that it wasn't high enough. This sort of doubt is very common in philosophy, which often worries about what we really know, for sure. It's also common in daily life in matters of extreme importance - the more is riding on us being right, the higher we tend to push T, and the more we realise that there is no objectively adequate place to set T. This sort of doubt looks like a request for more information, but it's not, because no information would suffice to ease our fears; it's probably only really resolved through therapy, or, as Hume says, backgammon.
4. Criterial doubts
Imagine you have all the information in the world except whether P is true. Well, if you know everything, you have all the possible evidence for and against P being true, so you can immediately deduce whether P is true, right? But not so fast. You know, say, Q. But unless Q is equivalent to P - for Q to be true is for P to be true, P and Q being true "means the same thing" - then you don't know P. And because Q is not in fact P, we cannot be sure it's equivalent. You can tell me "Q, therefore P", and I can say "I'm not sure that Q really entails P". I can doubt whether P and Q mean the same thing. I'm not asking for more evidence necessarily - I'm not saying you don't have enough evidence. I'm saying your evidence isn't evidence of the right thing. You can prove everything the world up to the edge of P, and I can still say "I accept all that, but I'm still not sure that P!". [Carroll's paradox and all that]. This is because I don't accept that Q, or Q+R or Q+R+S, or Q+R+S+T is really an adequate criterion for P. I can imagine P not being the case even when Q, R, S, T, U, V and so on all are the case. Not because I have evidence to the contrary, as in a conflict doubt. Or because I worry that there's some unknown information. But because I'm not sure that's what P means. So all the evidence you collect is useless, if it's evidence of the wrong thing!
We could alternatively call these: doubts from insufficiency; doubts from incommensurability; doubts from corrigibility; and doubts from synonymity. They tend to correspond to doubt-forms like, respectively, "I think we need more evidence", "I'm not sure how the evidence fits together", "I worry we may be missing something", and "I think we may be missing the point".