Никогда не доводилось слышать о таком правиле (про живых и умерших). Фамилия пишется перед именем и отчеством (или инициалами) в алфавитных пофамильных списках, в библиографии. В остальных случаях имя и отчество (а также инициалы) пишутся перед фамилией.

Вы задаете очень интересный вопрос. Сочетание король рок-н-ролла может осмысляться как прозвище и писаться по правилу о прозвищах так: Король Рок-н-Ролла или Король рок-н-ролла. Однако первый вариант не встречается совсем, второй очень редко. Сочетание осмысляется как описательный оборот, титул и пишется устойчиво без прописных букв. Возможно, на восприятие оборота влияет частое употребление его перед именем (напр.: За ним в рейтинге следуют известный гольфист Арнольд Палмер и король рок-н-ролла Элвис Пресли), а также то, что слово король в значении 'первый, самый лучший среди других, тот, кто достиг совершенства в чём-л.' закрепилось в русском языке (см. фиксацию в словаре).  

Корректно: заповедник «Три столба», «Томские стоянки».

Выделять имя знаками препинания не требуется. Вызывает сомнение только начало предложения: «Сейчас бывший чемпион...» Если есть возможность, слово «сейчас» лучше убрать.

Корректно: Джей Дабл-ю.

Возможно: Уважаемый господин Ким!

Инициалы – это графические сокращения имени и отчества. Графическое сокращение означает, что при прочтении слово читается полностью: мы не читаем [и-и-иванов], мы говорим либо просто Иванов, либо Иван Иванович Иванов.

В живой речи имя и отчество практически всегда предшествует фамилии (исключение – бюрократическая, канцелярская речь). Хорошая традиция – перенести этот принцип и в письменную речь.

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

К сожалению, мы не можем дать совет по делопроизводству - указывать номер телефона или нет. Что же касается пробелов, то они ставятся как между фамилией и инициалами, так и между инициалами имени и отчества.

По общему правилу имя деда не нуждается в обособлении: существительное дед — нераспространенное приложение, относящееся к имени собственному. Однако если существительное дед логически выделить и, как следствие, придать имени собственному характер попутного замечания, приложением станет уже имя собственное; такое приложение нужно обособить. (См. об этом параграф 63 полного академического справочника «Правила русской орфографии и пунктуации» под ред. В. В. Лопатина.) Таким образом, оба варианта расстановки знаков препинания корректны, но между ними есть смысловое различие. 

Лицо, которому запрещено что-то делать, является одновременно объектом запрета и субъектом запрещаемого действия. Если необходимо использовать выражение наложить запрет, то грамматически корректным будет использовать конструкцию, в которой имя этого лица связано с названием запрещаемого действия: на его выезд из страны наложен запрет. Если имя этого лица непременно нужно вынести в начало предложения (в позицию детерминанта) для того, чтобы дословно процитировать документ, можно рекомендовать использовать предельно абстрактный производный предлог в отношении: В отношении его «наложен запрет на выезд».