Ok, I just tried adding my @hotmail account with IMAP, and tried a server side search -- worked for me, although I only have a few dozen messages.
So, given this, would you record a debug log, capturing the issue? Give it some time to actually run server side search, and I'll need "raw session data" enabled in log settings as well.
For instructions, please see my signature, below.