Может, кто-то знает ответ на вопрос: можно ли как-то извлечь хистори чата для выбранного контакта в скайпе на новом компьютере (с чистой историей сообщений в чате)?

Нереально.
Хистори хранится на локальном компьютере в виде файла. Его нужно (или нужно было) скопировать по крайней мере. Тогда и открыть посмотреть его не проблема...даже не находясь в скайпе. Если на старом компьютере диск был отформатирован, то и хистори удалилась, естественно. Однако, если информация была удалена недавно, то есть небольшой шанс попробовать восстановить её с помощью специальных программ.

Хистори хранится у двух сторон, попробуй поговорить с другой стороной чата, у него должна быть. На сервере не хранится, на сервере только контакты

если ты ее не удаляла то история остается