Q: seems redundant to me. Is there a reason I should not remove it from every question title I come across?
Q: is, in some way, related to the question itself, it should be removed from question titles, after all, questions are the only thing that have titles!
If you don't have the reputation to edit questions without sending them through review make sure you check the body and tags of the question for other things that need fixing. The chances are, if the title contains
Q:, the body will have other things that need editing as well.
If you have the reputation to directly edit them, then yes, absolutely. As the only edit in the suggested edit queue, I'd vote to reject as Too Minor every time; removing 2 characters from the title isn't worth reviewers' time in my opinion.