I have a query on SSPR's functionality and I hope you can shed some light on that . In-order to make use of SSPR should the user perform atleast one successful login to the Office 365 services or can even a new user make use of it by visiting the SSPR site .
Note : When I say new user , it means that a user who has been newly on-boarded and has never accessed Office 365 at all .
the user will receive an error message when they attempt to reset their password if they have not successfully registered at least once with SSPR.
You can control how users register with SSPR by configuring registration to automatic, or if you set registration to none, then you can email the hyperlink to new employees informing them of the need and benefit of registering for SSPR. http://aka.ms/ssprsetup