Note: To fail the XFAIL test use the: make test TESTS="Zend/tests/type_declarations/ -j8 -d opcache.enable_cli=1" command.
I've narrowed down the problem to the inheritance cache, but I can't figure out where the issue is.

The Travis CI Failure can be reproduced with: make test USE_ZEND_ALLOC=0 TESTS="ext/reflection/tests/types/ --repeat 2 -j8 -d opcache.enable_cli=1 --asan"

On the XFAIL: OPcache expects class names in the dependency list to be shm-allocated / persisted. The name that fails the assertion was added to the list by track_class_dependency(), called by zend_is_intersection_subtype_of_class(), and comes from a method arg infos. Normally the class names in arg infos are persisted by OPcache before this step, but here it didn't happen. I think that we need to update zend_persist_type(): it doesn't appear to recurse in nested lists (zend_persist_type_calc() would need to be updated as well).

There are a few other places that may or may not need to be updated: zend_mark_function_as_generator, zend_type_permits_self, zend_declare_typed_property, and so on.

There could be a use-case for a ZEND_TYPE_FOREACH_CLASS_NAME() macro.

On the XFAIL: OPcache expects class names in the dependency list to be shm-allocated / persisted. The name that fails the assertion was added to the list by track_class_dependency(), called by zend_is_intersection_subtype_of_class(), and comes from a method arg infos. Normally the class names in arg infos are persisted by OPcache before this step, but here it didn't happen. I think that we need to update zend_persist_type(): it doesn't appear to recurse in nested lists (zend_persist_type_calc() would need to be updated as well).

So that was the issue, I was looking at the wrong place then.
I think I fixed the issues for that now then.

There are a few other places that may or may not need to be updated: zend_mark_function_as_generator, zend_type_permits_self, zend_declare_typed_property, and so on.

There could be a use-case for a ZEND_TYPE_FOREACH_CLASS_NAME() macro.

I'm not sure how a ZEND_TYPE_FOREACH_CLASS_NAME() macro would work as I think it's a general problem with ZEND_TYPE_FOREACH() which needs to cater to the nested types.

I will try to come up with test cases for every other instance as those probably do have some issue lingering in disguise

It's not letting me comment direcly on the patch, but I had some minor thoughts about making the parser a tiny bit more readable (less verbose):

union_type_element:
                type { $$ = $1; }
        |        '(' intersection_type ')' { $$ = $2; }
;

union_type:
		union_type_element '|' union_type_element
			{ $$ = zend_ast_create_list(2, ZEND_AST_TYPE_UNION, $1, $3); }
	|	union_type '|' union_type_element
			{ $$ = zend_ast_list_add($1, $3); }
;

And of course:

union_type_without_static_element:
                type_without_static { $$ = $1; }
        |        '(' intersection_type_without_static ')' { $$ = $2; }
;

union_type_without_static:
		union_type_without_static_element '|' union_type_without_static_element
			{ $$ = zend_ast_create_list(2, ZEND_AST_TYPE_UNION, $1, $3); }
	|	union_type_without_static '|' union_type_without_static_element
			{ $$ = zend_ast_list_add($1, $3); }
;

The lower verbosity may also help us out later when/if we add more complexity to algebraic types.

Note: This is not yet mentioned in UPGRADING / NEWS.