[Yadomaru]

Авито, не авито, это не важно. Если к сообщению, то контактные данные не обязательно есть уникальность, а значит либо регистрация, либо уже существует. А это означает, что пользователь также в базе под уникальным ID. Вот с этим ID и нужно ассоциировать файлы.
И тут в зависимости от того как организовано их хранение. К примеру, у каждого пользователя своя папка под изображения, значит файлы нужно перемещать в его папку, связывая каждый с ID сообщения.
Если наоборот, папки связываются с ID сообщения, то в нее помещаются файлы которые связываются по ID пользователя.
Ну и третий случай, общая папка (не совсем лучший вариант, если файлов в ней будет много), тогда в эту папку помещается файлы как связанные и по ID сообщения, и по ID пользователя.
Если формируемое имя файла прописывается непосредственно в базу, то могут быть еще варианты.
А у вас как все организовано хранение?

Проблема как раз в том, что регистрации нет. Пользователь просто вводит имя и прикрепляет файлы. Но прикрепление файлов и отправка имени происходит в разный момент. Как их связать? Может сессию открыть для каждого посетителя?

На счет самой организации папка с ID сообщения и туда файлы.