Have I missed something on the relationship field type?
Nope. That would be a hamstring, for sure.
How is your PHP? This really could be nailed down with a plugin. The plugin would run your SQL, and return a piped list of entry IDs that could then be used as a fixed order parameter for channel entries.