After hours of searching and trying I found out that on a x64 server the MSOnline modules must be installed for x64, and some programs that need to run them are using the x86 PS version, so they will never find it.
[SOLUTION] What I did to solve the issue was:
Copy the folders called MSOnline
and MSOnline Extended
from the source
C:\Windows\System32\WindowsPowerShell\v1.0\Modules\
to the folder
C:\Windows\SysWOW64\WindowsPowerShell\v1.0\Modules\
And then in PS run the Import-Module MSOnline
, and it will automatically get the module :D