Thought provoking.

Why have a service issue the GUIDs? A small bit of clr code could do what you need and would be fast. You could then let your insert stored procedures transparently create the "identity" of the record and return it to your middle tier layer.