There is a slightly convoluted workaround for finding most of your deleted posts, which doesn't require the 10,000 reputation necessary for using the deleted:1
search operator (of course, those users aren't likely to be post banned). It depends on the post being up- or downvoted, which creates reputation events, and those are visible even if they're long ago and have been reverted by deletion of the post.
Go to the reputation tab on your profile, check the 'show removed posts' option and use the pagination buttons at the bottom to navigate to the time around which you posted the question. Instead of having to open all date records manually, you can execute a small jQuery snippet in your browser console:
$("a.expander-arrow-small-hide").click()
If the post was voted on, it will show at least twice in the reputation history (maybe on different dates if the deletion, e.g. by Roomba, was later than the votes). Look for the word 'removed' and a non-clickable question title (it's only clickable if you have 10k reputation, in which case you don't need this workaround).

If the post received mostly downvotes, the reputation event will be positive (but a +1/-2 question will show -1 on the 'removed' event). If you downvoted an answer which was deleted, it'll show a +1 as well; if a user who downvoted your post was deleted, it'll show a +2 as well but with 'User was removed' instead of the question title.
There should be another event which the 'removed' event is cancelling; in the screenshot above, it's the "-2 19:33 downvote" one. That one is clickable, and you can navigate to it to determine if this was your deleted question you were looking for.