Temporal train test split for recommender systems
What I have previously done, and what have worked well in my domain (retail), is to first get a sense of the distribution of your user/rating frequencies. More specifically, say you want a test-set consisting of 10% of the observations, then figure out the threshold (n) where, if you take all users with at least n interactions, and their latest interaction(s), you end up with 10%-ish datapoints.
In your case, perhaps some fraction of the users have at least 5 interactions (ratings), then take the latest interaction(s) these users have done, and use that as your test-set (use more or less than 5 to change the size of your test-set). This way, there exists no users in your test-set that are not a part of your training-set, although, the users with very few interactions will not be represented in the test-set. This train/test-skew could also pose a problem, but not being able to provide recommendations for these users, I have found, pose an even larger problem.