Куки-то тут при чем? В новых браузерах столько всякого говна наворотили... Да и браузерный клиент не единственный вариант.

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

Поисковикам предоставить RDF и мета-теги. По ходу дела они сами разберутся, какие лучше. А Маша заглянет в профиль своего френда разлюбезного в своем локальном хранилище, да и тыкнется на следующий по списку сервер, с которым он контачит. Не говоря уж о том, что у нее у самой должен быть список не из одного сервера, причем по большей части совпадающий со списками ея френдов.