I've found the answer to my own question. Re-watching the WWDC'19 video "What's new in Universal Links", there was a tidbit mentioned:
Query items with no value and absent query items are treated by the operating system as if they have a value equal to the empty string. I haven't seen this documented anywhere else, but to assert the presence of the app parameter correctly you must use:
{
		"/": "/login/magic/*",
		"?": { "app": "?*" },
}
By requiring it to match at least one character forces the parameter to actually be a part of the URL. It's not clear how you would positively match a parameter that had no value. Luckily that doesn't apply in my case!
Topic:
App & System Services
SubTopic:
General
Tags: