Общий способ решения этой проблемы с использованием реляционной базы данных состоит в том, чтобы иметь таблицу списка, таблицу слов и таблицу слов таблицы, относящиеся к этим двум. Вы правы, что будут некоторые накладные расходы, но не переоценивайте их; поскольку структура таблицы определена, фактические накладные расходы на хранение каждой записи очень малы, и записи могут быть вставлены очень быстро.
Если вам нужны очень быстрые копии, вы можете разрешить копирование списков при записи. Это означает, что один и тот же список может ссылаться на один или несколько пользователей. Вы фактически дублируете список только тогда, когда пользователь пытается добавить, удалить или изменить запись. Конечно, это преждевременная оптимизация, начните с простого и добавляйте подобные сложности, только если вы считаете, что они необходимы.
Вы можете использовать хранилище значений ключей, как вы предлагаете. Я бы не стал пытаться создать его поверх текстового поля MySQL, если у вас есть для этого очень веские причины, так как любой поиск по ключу будет очень медленным, так как для этого потребуется поиск по строке. Хранилище данных со значением ключа, такое как CouchDB или Tokyo Cabinet, может сделать это очень хорошо, но, скорее всего, оно займет больше места (поскольку для каждой записи должна быть определена своя собственная структура, и каждое слово должно быть записано отдельно в каждом списке). Единственное измерение производительности, на мой взгляд, было бы лучше, если вам нужны масштабируемые операции чтения и записи, но это относится только к самой большой из систем.
Я бы наивно использовал MySQL и вносил подобные изменения только в том случае, если вам нужна производительность, и я могу доказать, что этот метод действительно будет быстрее.