Old question, but I just ran into this issue, so I came up with an alternate solution, inspired by the answer given by @kevnk

My solution is to replace all selects, site wide, but it can simply be adjusted to target specific selects.

This is done in magento EE 1.12, but I see no reason for it to work in other versions.

I created the following script which does the following:

1. Extends the `isValidation` method of Validation with a fallback to the original (now named `_isValidation`) The original will be called for anything other than select, or if a select does not have a matching chosen element 
2. Extends `insertAdvice` method of Validation. This purely changes the container to the matching chosen element, so the validation advice is placed after that
3. Listens to the chosen.change event to effect a new validation on the main select, to ensure validation errors go away. This has the side (positive) side effect that a validation error immediately appears if the selection is changed to none.

Simply include this code via layout to your site.

    document.observe("dom:loaded", function() {
        Object.extend(Validation, {
            isVisible : function(elm) {
                if($(elm).tagName == 'SELECT') {
                    console.log(elm.id.replace(new RegExp('-', 'g'),'_')+'_chosen');
                    if($(elm.id.replace(new RegExp('-', 'g'),'_')+'_chosen') != undefined) {
                       return true;
                    }
                }
                return this._isVisible(elm);
            },
            _isVisible : function(elm) {
                while (elm.tagName != 'BODY') {
                    if (!$(elm).visible()) return false;
                    elm = elm.parentNode;
                }
                return true;
            },
            insertAdvice : function(elm, advice){
                if($(elm.id.replace(new RegExp('-', 'g'),'_')+'_chosen') != undefined) {
                    var container = $(elm.id.replace(new RegExp('-', 'g'),'_')+'_chosen');
                } else {
                    var container = $(elm).up('.field-row');
                }
                if(container){
                    Element.insert(container, {after: advice});
                } else if (elm.up('td.value')) {
                    elm.up('td.value').insert({bottom: advice});
                } else if (elm.advaiceContainer && $(elm.advaiceContainer)) {
                    $(elm.advaiceContainer).update(advice);
                }
                else {
                    switch (elm.type.toLowerCase()) {
                        case 'checkbox':
                        case 'radio':
                            var p = elm.parentNode;
                            if(p) {
                                Element.insert(p, {'bottom': advice});
                            } else {
                                Element.insert(elm, {'after': advice});
                            }
                            break;
                        default:
                            Element.insert(elm, {'after': advice});
                    }
                }
            }
    
        });
    
        jQuery("select").chosen(
            {
                disable_search_threshold: 10,
                no_results_text: "Sorry, nothing found!",
                width: "100%",
                inherit_select_classes: true
    
            });
    
        jQuery("select").chosen().change( function(e){
            Validation.validate(e.target);
        });
    });

Hope this is of help to someone.