Правильно раздельное написание. Оно соответствует следующему правилу.

Недопустимо слитное или дефисное написание с приставкой или первой частью сложного слова, если вторая часть содержит пробел, т. е. представляет собой сочетание слов. В этих случаях слитные или дефисные написания, рекомендуемые основными правилами, должны заменяться раздельными. Например, следует писать: лже доктор наук, псевдо произведение искусства, теле круглый стол, мини стиральная машина; экс Советский Союз, псевдо Ван Гог, пол рабочего дня, пол столовой ложки, пол Московской области (Правила русской орфографии и пунктуации. Полный академический справочник / Под ред. В. В. Лопатина. М., 2006. § 153).

Предпочтителен вариант с родительным падежом.

Нужно писать раздельно. Вот общее правило на этот счет:

"Недопустимо слитное или дефисное написание с приставкой или первой частью сложного слова, если вторая часть содержит пробел, т. е. представляет собой сочетание слов. В этих случаях слитные или дефисные написания, рекомендуемые основными правилами, должны заменяться раздельными. Например, следует писать: лже доктор наук, псевдо произведение искусства, теле круглый стол, мини стиральная машина; экс Советский Союз, псевдо Ван Гог, пол рабочего дня, пол столовой ложки, пол Московской области; то же в парных конструкциях с полу: полудеревни — полу дачные посёлки, полусанаторий — полу дом отдыха, полупародия — полу литературный фельетон, полуясли — полу детский сад".

Недопустимо слитное или дефисное написание с приставкой или первой частью сложного слова, если вторая часть содержит пробел, т. е. представляет собой сочетание слов. В этих случаях слитные или дефисные написания, рекомендуемые основными правилами, должны заменяться раздельными. Например, следует писать: лже доктор наук, псевдо произведение искусства, теле круглый стол, мини стиральная машина; экс Советский Союз, псевдо Ван Тог, пол рабочего дня, пол столовой ложки, пол Московской области.

При этом в сочетаниях экс-сотрудник ЦРУ, экс-глава ФСИН вторая часть сложного слова представлена одним словом (сотрудник, глава), т. е. возможно самостоятельное употребление сочетаний экс-сотрудник, экс-глава. Таким образом, правило о замене дефиса пробелом не распространяется на эти слова.

Рекомендаций для подобных случаев в справочниках по правописанию пока нет. Из предложенных Вами вариантов лучше второй. Он выглядит диковинно, но не искажает названия, как в первом варианте. Однако более предпочтительным представляется написание без знака препинания: А ты «Мертвые души» то читал?  Когда приставка или часть сложного слова, требующая слитного написания, присоединяется к словосочетанию, она пишется раздельно. Ср.: лже доктор наук, псевдо произведение искусства, теле круглый стол, мини стиральная машина; экс Советский Союз, псевдо Ван Гог, пол рабочего дня, пол столовой ложки, пол Московской области. Это правило можно распространить и на написание постфикса то, присоединяемого к словосочетанию. 

Спасибо за очень интересный вопрос. Мы передадим его в Орфографическую комиссию РАН.

Ответить на Ваш вопрос мы попросили д. ф. н. М. Я. Дымарского.

В решебнике написано верно. Количественно-именные словосочетания (много снега, множество решений, пять книг, тьма проблем и т. п.) всегда являются одним членом предложения. Существительное множество изменяется по числам (формы мн. ч.: множества, множеств, множествам и т. д.). В приведенном предложении оно использовано в форме ед. ч. И. п., поэтому согласование с ним глагола в форме ед. ч. абсолютно правомерно. Сказуемое согласует свою форму с главным компонентом словосочетания, являющегося подлежащим.

Да, такие правила существуют. Они называются правилами координации. Вот выдержка из этих правил.

Недопустимо слитное или дефисное написание с приставкой или первой частью сложного слова, если вторая часть содержит пробел, т. е. представляет собой сочетание слов. В этих случаях слитные или дефисные написания, рекомендуемые основными правилами, должны заменяться раздельными. Например, следует писать: лже доктор наук, псевдо произведение искусства, теле круглый стол, мини стиральная машина; экс Советский Союз, псевдо Ван Гог, пол рабочего дня, пол столовой ложки, пол Московской области. (Правила русской орфографии и пунктуации. Полный академический справочник / Под ред. В. В. Лопатина. М., 2006.)

Однако сочетание (лже) крымское шампанское может быть понято двояко и, соответственно, иметь разные написания. Лже крымское шампанское – это какой-то напиток, выдаваемый за крымское шампанское (лже + крымское шампанское), лжекрымское шампанское – это шампанское, которое сделано не в Крыму, но выдается за крымское.

Ваше предположение верно: по имени Валя — приложение. Такие приложения, согласно параграфу 64 полного академического справочника «Правила русской орфографии и пунктуации» под ред. В. В. Лопатина (М., 2006 и след.), обособляются, но могут и, согласно примечанию 1 к этому параграфу, «не обособляться, если они имеют основное, выделительное значение, т. е. не являются уточнением или пояснением впереди стоящего определяемого слова: Завел он себе медвежонка по имени Яша».