Probably we can just store the name of local (non-exist) pages in Wikidata.

e.g. https://en.wikipedia.org/wiki/Gymnopogon_doellii does not exist:

1. Store en:Gymnopogon doellii to https://www.wikidata.org/wiki/Q15518032 like ordinary sitelinks
2. When someone view https://en.wikipedia.org/wiki/Gymnopogon_doellii, the placeholder page will be shown
3. Links to Gymnopogon doellii in enwiki will be shown in another color (probably purple/violet). When the link is clicked, the placeholder page will also be shown
4. When someone created en:Gymnopogon doellii, all links to this page will turn blue. no changes is needed in Wikidata. When en:Gymnopogon doellii is deleted, the admin can choose whether the sitelink should be deleted. (Yes if it is considered non-notable and No if it is deleted because it is a nonsense/test/copyvio but can be a future topic). If the sitelink is deleted the page will become a normal non-exist page (and if the page is restored, it is T75908: Avoid lost link for deleting pages which are later restored); If the sitelink is not deleted the page will become a placeholder page again.
5. If there're no given placeholder sitelink in a item, the placeholder can not be viewed from trying to view a non-exist page, but can still be reached via special pages or searchs.

Selecting which item is relevant to the title in question is the first step and can follow a wdsearch approach. The only problem is how to make users report/solve disambiguation issues, but in the end having an unexpected topic under a certain title is business as usual.

The second step is to decide whether to display a placeholder at all, regardless of its technical quality. One basic criterion is that the item must have at least N sitelinks or M sitelinks to the same project (e.g. to Wikiquote wikis if on Wikiquote, or to Wikipedia wikis if on Wikipedia). N = 1 may be reasonable, but maybe a careful beginning would look like M = 1, N = 5.

The third step is improving how the placeholder is packaged and shipped, for instance how the red links should look like (still action=edit? different shade of red?) and how to change [[MediaWiki:noarticletext]] and friends (should it still be a 404, or return 200? should it be indexed? what's the canonical URL? how to provide a sitemap?).

@Lokal_Profil mentioned that you probably want to have the red links title as the suggested page title instead of the Item's label. That's something to keep in mind.

Why invalid?