When I downvote, it says
Thanks for the feedback! Votes cast by those with less than 125 reputation are recorded, but do not change the publicly displayed post score.
But when I check my profile, I cannot find the questions/answers I downvoted.
That's because you haven't downvoted the post. You've provided feedback (in a form separate from traditional voting), but you are unable to actually downvote until you have 125 rep.