Train-Test split for a recommender system
My two cents,
Evaluating results of a recommendation engine where test-set is unseen users only, will allow you doing exactly that.
Evaluating results on unseen users only.
If this is indeed the motivation(product/business wise) behind your recommendation engine I would suggest trying to tackle this problem directly.
If evaluating performance on 'unseen' users is an additional metric and not the only one I would keep with current scope of train/test splitting(which should create some unseen users in the test set). 

Regarding methods on how to best recommend to unseen users, your intuition(K-nn) is one common solution.
 See this for example