Get random entries, excluding an array of entry IDs, where a relational field is not empty
That seems to be a bug / limitation of the :notempty: statement, it's probably adding its own ID criteria in the background and the merge doesn't work as expected. I'd suggest you file a bug report.

In the meantime you could just add the "not empty asset field" criteria making use of the relatedTo parameter as a workaround. See How can I get only those entries with non-empty assets field for example code.