The search probably runs off a separate full-text index in their back-end (an inverted index if you will). When people post public tweets these probably get enqueued to be added to the index, so they will be included in search. They just need to delete all tweets from the index an account once it's made private. Maybe their index is append only, or it's very computationally expensive to remove old records (which is usually true for these data structures), so they've opted not to do this yet.