お引越しする is different from a humble form "お + the -masu stem of a verb + する" like お聞きする, お尋ねする. This is just a polite form(美化語) of a -suru verb 引越しする, as same as お食事する, お洗濯する. In fact, ~にお引越しする doesn't imply respect towards the target に indicates, i.e., the place you move to.
Isn't this also an answer to Glenn-san's question?;-)