Modeling bill/ship addresses

I've been going back and forth on the best way to model this.

A user can have one to many bill and ship addresses.
An order can have one bill address and one to many ship addresses

Let's assume I have a single address table, with an address_type
column that is a foreign key to the address_types table.

Now to create the relationships between addresses and users/orders.  I
 could create a join table for holding the addresses that belong to
orders.  For example table order_addresses that has order_id and
address_id columns that are foreign keys on addresses and orders.

But what about just having two foreign keys in addresses?  order_id
and user_id?  Or is there a rule against having a null foreign key?

Also, is there a good database independent way to make the address
immutable once it's created?  I don't mind doing it at the application
level actually, as I'm using a MVC framework that makes it easy to
define that logic once in the model instead of spread out all over the
codebase.

Chris