updatedb would probably be best rewritten.   I'm going to mark the updatedb-related bus as "Postponed" in order to consider them all in a batch, when I get around to the rewrite.

(Leslie P. Polzer did start on a rewrite some time back as part of the Summer of Code but there are some updatedb-related issues his changes don't resolve yet, I think)

I like the idea of using .locatedb for the mounted directories. But why stop at that? Why not implement, that if a directory contains a file called .locatedb then it should be assumed it contains the database for the subtree under this dir?

It should then simply be merged into the main locate database.

I got this idea when my machine was highly irresponsive due to running updatedb on a huge directory structure that only changes once every month (and therefore is almost read-only).

A configuration file is a good approach for dealing with read-only
media (CD-ROMs) or with volumes that are offline (a collection of
CD-ROMs, for example).

However, it doesn't answer the usecase of NFS mounted volumes properly.
I mean, I use mount/umount typically twice a day, plus plugging in
USB sticks volumes as well. It's not realistic to expect that a user
will update a configuration file each time he mounts or unmounts a
volume. So it should be the 'mount' program which updates the configuration
file automatically. If you get these changes accepted by the 'mount'
maintainers - fine with me. But there's already an agreement that
'mount''s modifications to /etc/mtab are an anachronism, because /proc
(or system calls) provides the same information in a more accurate way.
Therefore I think it's worth thinking about a solution that works without
cooperation from the user or from the 'mount' program.

Regarding newline in pathnames: I think this is an irrealistic requirement.
We are talking about mountpoints here. Such mountpoints are usually listed
in /etc/fstab, where (AFAIK) no provisions for escaping, newlines, not
even spaces, are made.

The updatedb / locate approach is unusable in practice on
systems with large (> 1 GB) NFS mounted volumes, simply
because of the limited speed of 'find' over NFS.

Here is a suggestion for making it work in this situation as well:
Declare that it must be the server's responsibility to maintain
the locatedb at a fixed location under the mountpoint, for
example at  {mountpoint}/.locatedb.
1) Define precisely this location, {mountpoint}/.locatedb or so.
2) Change the 'locate' program so that it looks not only in the
global /etc/locatedb, but also iterates over each NFS-mounted
filesystem and looks there as well.
3) Provide an updatedb-exports script, intended to be run on
the server, that iterates over all NFS-exported volumes
(showmount -e) and updates the .locatedb there.
4) Explain all of it in the documentation.