If Microsoft's scan is a server-side scan, how do they scan "everything" if "everything" includes things that you do not upload?

By your definition of "everything", both Microsoft and Apple scan "everything". (Or Apple will, after this new system is rolled out.)