Mohu mít primární klíč bez seskupeného indexu? Mohu mít také vícehodnotový seskupený index?

(Tato odpověď je pouze pro SQL Server 2005+. O MySQL nic nevím.)

Ano. Jak jste zmínili, omezení primárního klíče je standardně podporováno seskupeným indexem. SQL Serveru můžete říci, aby omezení podpořil neklastrovaným indexem tak, že omezení deklarujete takto:

ALTER TABLE MyTable
    ADD CONSTRAINT PK_MyTable
        PRIMARY KEY NONCLUSTERED(Col1);

Ano, můžete definovat index s více než jedním sloupcem v klíči indexu. Opravdu se neliší od neshlukovaného indexu.

CREATE UNIQUE CLUSTERED INDEX IX_MyTable_Clus
    ON MyTable(Col1, Col2, Col3);

Reference:ALTER TABLE , CREATE INDEX