MySQL refuses UPDATE with (1071, ‘Specified key was too long; max key length is 1024 bytes’) sometimes

I'm using MySQL 5.7.2.23.

I need to copy some columns between two tables (u -> m) and I am using the following update command:

UPDATE m 
 JOIN u 
  ON u.id=m.user_id  
  AND u.package_name=m.package_name 
 SET 
    m.host_version = u.host_version,
    m.device_model = u.device_model,
    ...
     m.device_name = u.device_name 
 WHERE    shard_id = 96

The UPDATE works

Both tables have keys on (id, package_name):

CREATE TABLE u (
  id` varchar(255) COLLATE utf8_unicode_ci NOT NULL,
  package_name` varchar(255) COLLATE utf8_unicode_ci NOT NULL,
  device_model` varchar(255) COLLATE utf8_unicode_ci DEFAULT NULL,
  device_name` varchar(255) COLLATE utf8_unicode_ci DEFAULT NULL,
  host_version` int DEFAULT NULL,
  shard_id` int NOT NULL DEFAULT '0',
  device_group_id` int DEFAULT NULL,
  PRIMARY KEY (shard_id`,`package_name`,`id`),
  UNIQUE KEY by_id` (`id`,`package_name`),
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci

CREATE TABLE m ( 
  user_id varchar(255) COLLATE utf8_unicode_ci NOT NULL,
  package_name varchar(255) COLLATE utf8_unicode_ci NOT NULL,
  device_name varchar(255) COLLATE utf8_unicode_ci DEFAULT NULL,
  device_model varchar(255) COLLATE utf8_unicode_ci DEFAULT NULL,
  host_version int DEFAULT NULL,
  PRIMARY KEY (package_name,user_id),
  UNIQUE KEY by_id (user_id,package_name)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci

Innodb default row format is innodb_default_row_format=dynamic and
Innodb innodb_large_prefix=ON.

And yet for some shardId-s I get the above error message (key too long).

Explain shows the following

id            | 1
select_type   | SIMPLE
table         | u
partitions    | <null>
type          | ref
possible_keys | PRIMARY,by_id
key           | PRIMARY
key_len       | 4
ref           | const
rows          | 5
filtered      | 100.0
Extra         | <null>

id            | 1
select_type   | UPDATE
table         | m
partitions    | <null>
type          | eq_ref
possible_keys | PRIMARY,by_id
key           | PRIMARY
key_len       | 1534
ref           | activitydb.u.package_name,activitydb.u.id
rows          | 1
filtered      | 100.0
Extra         | <null>

I understand that the key is 1534 due to 3-byte UTF-8 encoding and changing the columns to latin1 reduces the key length and solves the problem.

What I don't understand is why MySQL complains only on some shard_id values. The shards that do work seem to have a very small number of rows.

And in general we use the above JOIN for many SELECT queries and MySQL does not complain about key length.