How to design and evaluate video recommender system from implicit click feedback?

I have a video click data set with records coming in, in the following format.

user, video, timestamp

I would like to build a recommender system to predict videos for users. I have some basic questions about the several approaches that could be followed and issues with each of these approaches.

1. [Non-Temporal Models - Approach 1] Here, I ignore the timestamp and just prepare the data as user, video, counts_of_watches.
2. [Non-Temporal Models - Approach 2] Here again, I ignore the timestamp, but only consider implicit feedback (user clicks). So the data is prepared as pairs user, video. Matrix Factorization with ranking losses can be used on such type of problems (latent collaborative retrieval).
3. [Non-Temporal Models - Approach 3] Ignoring the timestamp again, I treat the problem as binary matrix factorization. Positive samples are the true clicks observed user, movie, 1 and negative samples user, movie, 0 are decided based on some knowledge of how the videos were presented in the UI (e.g. all videos positioned above the click position are taken as negative samples). For this, I use a collaborative MF method with square loss and RMSE measure.
4. [Non-Temporal Models - Approach 4] Same idea of creating a binary MF dataset as in approach 3, but to create negative samples, we use NCE (noise contrastive estimation). This is also suggested in one of the answers in the thread: Matrix Factorization Recommendation Systems with Only "Like" Ratings
5. [Temporal Model] Here I make use of the data with timestamps and prepare the implicit click data as user, movie, timestamp. Sequential models like RNN, LSTM based Deep NNs could be used here.

Issues I observed with the above approaches:

• There is a heavy power-law behavior in the click data in real world problems (phenomenally huge # of users tend to click on only one video). This affects the model that is being learnt. How to deal with it? If I try to chop-off the tail (ignore all users or videos with only 1 click), then the training data size reduces dramatically. Not sure if this is a right approach either.
• The data does not consist of any explicit feedback (no ratings, only implicit feedback of whether they watched and at what time). So not sure how to use latent MF models which are based on square loss and RMSE metrics. Even if we do create a binary MF dataset (as described in approach 3 above), it doesn't make sense to use a square loss. A classification based (logistic) or a ranking loss seems more natural for this.
• It is also not clear how to define evaluation metrics like precision@k, recall@k for implicit feedback models.

Appreciate any thoughts, suggestions on this modeling problem and the issues described above. Any comments on the approaches I mentioned above and why they may / may not work?