complex mysql constraints over foreign keys
ALTER TABLE orders
  ADD FOREIGN KEY (user_id, address_id)
      REFERENCES address (user_id, id);


A single row then cannot have a user_id and address_id that do not appear on a row together in the address table.  

Yes, I would say you want such a constraint.