It would help to see the segment definition, but my assumption is that you're seeing Paid Search because of the persistence (expiration) of the marketing channel report (default setting is 30 days, I believe). Either that, or you're looking at visits/visitors who have encountered multiple marketing channels during the reporting window and your segment isn't set up to properly exclude what you think it's excluding.