Does anyone know where Outlook stores the "first day of the week" field
for calculating recurring appointments?

I can tell you based on testing (ask me if you want to verify the test
steps) that Outlook DOES store the "first day of the week" setting in
each appointment record. You can change this setting via
Tools-Options-Calendar Options, which usually defaults to "Sunday" as
the first day of the week (at least where I'm from). If you add a
recurring item, then change this setting, then add the exact recurring
item again, you'll notice that the new item uses the new setting for
calculations, while the old one continues to use the old setting (so it
must be saved somewhere in each record).

I used Outlook Spy to compare all of the fields of the before and after
items, COM and MAPI, but didn't find any differences other than the ID
and some of the date/time stamps. Nothing like I would expect to find,
like a "0" for Sunday, and a "1" for Monday, or something like that.

I have some code which duplicates Outlook's calculations, and without
access to this field I can't correctly duplicate it. They give access
to all of the other fields I need, in the RecurrancePattern COM object.
I didn't see that that object has a MAPIOBJECT interface though, so
I'm not sure if I can get access to "undocumented" fields like I can
with the MAPI appointment item itself.