1. I did create a permission set and assigned it to the user like it was mentioned. 

2. Even logged in using the two-factor authentication method, but not through Salesforce Authenticator app( because that option never came in 10 times I logged In/out), I got through OTP on the phone. 

3. On identity history, I can see the transactions as well. 

However, still, it is showing challenge not complete. Is there any reason another way to validate it. 
"Challenge Not yet complete... here's what's wrong:
Could not find a user's successful login using two-factor authentication. Make sure you successfully log in at least once and that you are prompted for the second factor of authentication."

 

To Crosscheck, 

1. I did make sure I am verifying and logged in in right org.

2. Checked that the user/Profile defined on permission set and user login are same.

3.  Did cross-check on session setting as well.

 

I think the solution would be, to verify by Salesforce Authenticator App. But how to get that option when login from the desktop.