They'll come around. Outlook users already (try to) use search, because sorting alone never works. So they'll use Gmail search and over time come to see that it's so good, they'll just stop explicitly organizing.

I know I did. I was tagging everything when I started using Gmail. Now, I don't even bother.

This is one of those features you only add to make converts feel at-home.