Jason,
I've tried what you suggested (and what seems a VERY good idea) :
assign a primary key in the insert trigger, but I have 2 problems with it :
1. the insert trigger doesn't allow me to change the record, don't remember the exact message but there seems to be a problem with recursive calls of rule expression(s). When I try to do the same in the record rule : it works. Could it be that you also assign the prmary key there instead of the ins trigger ?
2. it seems to me that you may encounter problems with deleted records if you use the procedure to create a new PK (newid) as you suggest : look at the highest used PK and add one to it : if you have SET DELETED ON (as most of us do, I suppose) and the record with the highest used PK has been deleted, it's PK will be reused, and the PK won't be unique ! I use another system to determine the PK, but I was just wondering how you solve thisone ?