Supervised Recommendation System trained on labeled phrase segments
CNN-Text-classification. Try this. Keep in mind that a deep learning algorithm will require a large data-set if you want a good accuracy. Since you want to give ranked recommendations to the users, a soft-max layer at the end will give you the probability of the phrase belonging to all the classes, so you can rank the labels in the order of the probability and suggest them to the user. 

Your first approach is the simplest and best given that you have finite data. I don't think it will be very scalable as your data grows. Also this approach will work best only when your phrases are so limited in their context and vocabulary. Using a convnet you can train on bigger and more ambiguous phrases and get good predictions.