Recover deleted user from Office 365

Connect to MSOnline using powershell and run the code:

Restore-MsolUser -UserPrincipalName user1@o365info.com -AutoReconcileProxyConflicts -NewUserPrincipalName user1@o365info.com

Source: o365info.com