  Distributed applications are commonly based on overlay networks
interconnecting their sites so that they can exchange information. For these
overlay networks to preserve their functionality, they should be able to
recover from various problems like membership changes or faults. Various
self-stabilizing overlay networks have already been proposed in recent years,
which have the advantage of being able to recover from any illegal state, but
none of these networks can give any guarantees on its functionality while the
recovery process is going on. We initiate research on overlay networks that are
not only self-stabilizing but that also ensure that searchability is maintained
while the recovery process is going on, as long as there are no corrupted
messages in the system. More precisely, once a search message from node $u$ to
another node $v$ is successfully delivered, all future search messages from $u$
to $v$ succeed as well. We call this property monotonic searchability. We show
that in general it is impossible to provide monotonic searchability if
corrupted messages are present in the system, which justifies the restriction
to system states without corrupted messages. Furthermore, we provide a
self-stabilizing protocol for the line for which we can also show monotonic
searchability. It turns out that even for the line it is non-trivial to achieve
this property. Additionally, we extend our protocol to deal with node
departures in terms of the Finite Departure Problem of Foreback et. al (SSS
2014). This makes our protocol even capable of handling node dynamics.
  This is the full version of a correspondent paper published at OPODIS'15.
