Which one is correct?
- He should have express shipped it to me.
- He should have it shipped express to me.
The only way I can parse he should have express shipped is to regard express shipped as the past of a compound verb express ship (which I would hyphenate). This is perfectly understandable, but it is not, as far as I know, an established word or phrase, so I would not use that form in any formal context.
Both are fine. In the first case, to express ship is a set phrase, as we might say to green light. In the second, express gives the method of shipping, as we might say to fly first-class.
Such verbs cannot arbitrarily be inverted, however; in fact, I have a hard time thinking of another that can be, from air drying my mushrooms (but not drying my mushrooms air) to zebra striping my spreadsheet (but not striping my spreadsheet zebra).