Todas las tablas de una base de datos deben tener obligatoriamente un PRIMARY KEY??

[Mithrandir]

Teoricamente no, aunque practicamente diría que sí. Eso te quita de problemas, por ejemplo en SQL Server puedes tener mensajes de ambiguedad difíciles de lidiar.

Si no tienes campos suficientemente unicos, entonces considera una llave autoincremental. Mi recomendación es que siempre te preocupes por tener una PK.