The effect of a Primary Key on a blocking situation
Community wiki answer - please edit to improve:

The reason is when you create an index, either specifically or by declaring it as primary key (which internally creates an index to enforce the constraint), it makes both update statements fast, and they finish quickly without blocking.

With no index, each query has to scan all the records to locate what you have specified in the where clause, and thus there is blocking, which I guess would eventually go. Or it's lock escalation: without the index, it has to escalate to a table lock, and that's what blocks. You really need to look at what resource is being held by the block/deadlock to see what is happening.