I don't see any evidence of there ever having been an autolink regex for CQ-DEPEND lines. Is this supposed to work? What makes you think that stars before change-ids would cause it to autolink to a different host? Is this documented anywhere? Where?

I don't know about evidence ;-) but if you open this URL for instance https://chrome-internal-review.googlesource.com/#/c/chromeos/vendor/mali-ddk/+/576977/ you can see clickable links created from Change-Ids.
It also works when you use CQ-DEPEND=CL:[*]cl_number notation. 
Everywhere in gerrit * (and cbuildbot too) is used as notation for marking internal changes that go to chrome-internal-review instead of chromium-review. It is not regex expression.

You can see for instance this CL for example on how CQ-DEPEND with star works https://chromium-review.googlesource.com/#/c/chromiumos/overlays/chromiumos-overlay/+/912048/ and takes you to internal server.

The problem is this does not work properly in Gerrit when using Change-Id instead of CL:xxxx or CL:*xxxx notation.

I see, so this isn't a regression, it's a feature requests to support the * syntax in more forms.

Are there places where the * form points from chrome-internal to chromium? Or is it only used on external reviews to indicate that the item it internal?

For future reference, it is regexes. The way those hyperlinks are automatically generated is via a set of regexes which are stored in the Gerrit host's base configuration. Some of the regexes (like automatically linking "I<40 character sha1>" to a change-id on the same server) are built-in to gerrit itself, while others (like automatically linking "CL:*123456" to a review on the internal host, or linking Bug: lines to Monorail) are custom specified by our own configuration.

CL with star always creates a link to internal gerrit CL
CL without star always points to external open source gerrit
For instance this is an internal CL that has dependency on external (open source) CL https://chrome-internal-review.googlesource.com/#/c/chromeos/overlays/project-cheets-private/+/567098/
Star is always used to denote CL that resides on internal gerrit.

Those statements are not universally true; for example, on the change you just linked to, the Change-Id without a star links to the internal host.

It looks to me like there's good support for "CL:123" and "CL:*123", but not for change-ids. Do people expect this to work for change-ids? I don't believe it has ever worked for change-ids.

I guess they are not universally true.

On this change https://chrome-internal-review.googlesource.com/#/c/chromeos/overlays/project-cheets-private/+/567098/
CQ-DEPEND=CL:912048 links to https://chromium-review.googlesource.com/#/q/912048

Change-Id in Change-Id: line links to internal host as expected.
I am askinga about Change-Ids in CQ-DEPEND lines. Not in Change-Id line.

I expect it (star) to work for change-ids in CQ-DEPEND line.
Otherwise it is not possible to upload changes with CQ-DEPENDS at upload time.
One would have to upload changes, look for CL numbers in both gerrits, add CQ-DEPENDS and re-upload changes again.

Moving this over to the chromium project.

Moved issue gerrit:8492 to now be issue chromium:821094.