You were on the right track. I would create a view in the relational database or a named query in the DSV containing as the single column the distinct non-null order IDs, maybe call it "DimOrderId". Then build a dimension from it, setting the "Null processing" property (you have to click the "plus" two times for the "Key Columns" property of the attribute in BIDS to access this property) to "UnknownMember".
And then use this dimension for the many-to-many relationship.