Have you tried the new ComboBox control in CRM 2013? Wait...what did you just say?!? Here, click on the screenshot and watch this:
Actually, I'm a little early for April Fools' Day, but I really did build a pair of ComboBoxes that are backed by two entities that have an N:N relationship. With an added checkbox, you can override the filtering and display all the available records in the child. The key to making it so performant was utilizing an external WebAPI caching application. That makes it a snap to bind the jQuery Autocomplete to the JSON output.
If you need help with a ComboBox, or anything else in Dynamics CRM, don't hesitate to reach out.