We study the bidding strategies of vertically differentiated firms that bid for sponsored search advertisement positions for a keyword at a search engine. We explicitly model how consumers navigate and click on sponsored links based on their knowledge and beliefs about firm qualities. Our model yields several interesting insights; a main counterintuitive result we focus on is the "position paradox." The paradox is that a superior firm may bid lower than an inferior firm and obtain a position below it, yet it still obtains more clicks than the inferior firm. Under a pay-per-impression mechanism, the inferior firm wants to be at the top where more consumers click on its link, whereas the superior firm is better off by placing its link at a lower position because it pays a smaller advertising fee, but some consumers will still reach it in search of the higher-quality firm. Under a pay-per-click mechanism, the inferior firm has an even stronger incentive to be at the top because now it only has to pay for the consumers who do not know the firms' reputations and, therefore, can bid more aggressively. Interestingly, as the quality premium for the superior firm increases, and/or if more consumers know the identity of the superior firm, the incentive for the inferior firm to be at the top may increase. Contrary to conventional belief, we find that the search engine may have the incentive to overweight the inferior firm's bid and strategically create the position paradox to increase overall clicks by consumers. To validate our model, we analyze a data set from a popular Korean search engine firm and find that (i) a large proportion of auction outcomes in the data show the position paradox, and (ii) sharp predictions from our model are validated in the data.