How does partitioning and the lack of a primary key affect ON DUPLICATE KEY UPDATE Consider a table with the following columns:

phone BIGINT NOT NULL PRIMARY KEY,
name VARCHAR(64),
state VARCHAR(64)


We would like to partition the table on state, however that would require dropping the primary key constraint on phone and replacing that constraint with a UNIQUE constraint. We make use of INSERT ... ON DUPLICATE KEY UPDATE and I would like to know how it would affect the system. Surprisingly little is written on the subject from reliable sources, and I'm sure that there are hidden gotchas which will not be immediately apparent to my naive eye.

What problems might we encounter with a partitioned table lacking a primary key, especially in regards to INSERT ... ON DUPLICATE KEY UPDATE queries?

The database in question in running MySQL 5.5 on Amazon RDS. The table in question has upward of 20 million rows and is often used in JOINs with other similarly-sized tables.
When we talk about partitioning tables in relational database platforms is recommended that it is always done on tables where the field is numeric. As a suggestion I would create an additional field that would serve as a surrogate key and this in turn would be used for partitioning the table.