Confirmed by Microsoft:
“Content Search is not available on Office 365 right now, but we are working on enabling it in the future.”
Source:
http://sharepoint.microsoft.com/blog/Pages/BlogPost.aspx?pID=1053
Let’s hope this web part comes available as soon as possible!