Подскажите пожалуйста, как правильно уволить нерадивого и неадекватного работника?

Поминутно проанализируйте его работу, его обязанности, рабочее место, дайте задание, которое он не выполнит, затем - еще одно, с секундомером следите за его приходами-уходами и перекурами, за каждую промашку составляйте акт и требуйте письменных объяснений и влепляйте выговор - за систематические опоздания и неисполнение служебных обязанностей. Два выговора - увольнение по статье. И объясните ему, что пока готовится приказ, он вправе уволиться по собственному желанию, и даже без двухнедельной отработки. Если дрогнет, напишет - по собственному - ликуйте и в ту же минуту увольняйте, пока не отозвал заявление. Это он уже не оспорит.
Вы с ним уже раз прокололись, не допускайте сейчас ошибок. Прибегните к помощи какого-нибудь матёрого аппаратчика.
Не забудьте ему окончательный расчет сделать и уведомление направить, чтобы трудовую книжку забрал.
В конце концов, если не получится - сокращайте должность. Все равно на этом месте он работу не производит.
Но, подозреваю, если у вас в конторе его ТД нет, то и должностной инструкции с его подписью нет. Кстати, возможно, он оба экземпляра ТД стырил и у себя держит. Тогда сложно будет неисполнение обязанностей ему вменить - а что он вообще обязан-то.. . В каком подразделении числится, какому руководителю подчиняется, чьи и какие указания выполняет.. . Проходил ли повышение квалификации, не представлял ли подложных документов при поступлении на работу, выполняет ли требования по охране труда и пожарной безопасности.. . Листок нетрудоспособности его, кстати, тоже проверьте, свяжитесь с поликлиникой, не поддельный ли. Подсчитайте - из отпуска он вернулся - не прихватил ли лишний день, а то ведь прогул.
Вот будет повод и у Вас бардак в документах подчистить.

Нерадивый-почему? Если есть нарушение трудовой дисциплины. по каждому шагу нарушения составляйте акт и просите объяснительные. Хотя если он у вас по суду восстановлен, то человек бывалый. У нас был такой случай, пришлось пойти на то что бы сократить должность и работника.

С каждой сменой руководителей не требуется перезаключать ТД.
Так что его старый ТД действителен.

Дать ему задание с которым он точно не справится, или провести аттестацию на проф. Пригодность, а там завалить.