Александр Юдаев

Рассмотрим другой пример: процедура поиска чего-нибудь. Мы ищем ищем, и не можем найти. Каким способом сообщить причину неудачного поиска? Вернуть в этой ситуации можно пустой список или null.

Если мы ничего не нашли, то выводим просто пустой список. И это логично, Вы ведь искали что-то по корректному списку, ничего не нашли, поэтому вернули пустой список.
Если же при попытки поиска по данным произошло что-то нештатное (БД отвалилась, файл перестал читаться и т.д.), то нужно выкидывать исключение, ловить его и обрабатывать. Пользователю тоже желательно показать. что произошла ошибка.

Какая-то непонятная формулировка задачи.
Если говорить о сервисах (службах) в Windows и демонах в Linux, то можно использовать либо QtService, либо mono-service на C#. Но что-то мне подсказывает, что эти решения не будут работать на iOS и Android (хотя ручаться не могу).
Вообще, службы винды — достаточно специфичная штука, и если вдруг вы потом захотите через нее как-то обращаться к GUI, то ничего не выйдет.

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

Найденный Вами алгоритм Navigation Mesh — пожалуй, самый лучший вариант на текущий момент. Его, например, использует движок Unreal Engine.
Еще можно посмотреть на алгоритмы AA*, HPA*, HAA*, они учитывают размер объекта. Недавно как раз была статья.