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