Hi,
Allow ordering out-of-stock products is the default setting. However, you can override that in every Product itself. So go to one of your products that have been ordered even its out of stock and check the quantities pages. Availability Preferences overrides the default settings and make sure "Use default" is selected.