I noticed the same problem again with a new store.

Used a db from another store, emptied all address, customer and order tables.

Now everything is set for the new store- tested a order and it did not show up. It turns out that I deleted the order status table as well.

I had to insert order status values under Localisation - Order Status. Used Pending, Processing and Shipped.

Now everything works as expected.

Hope this will help someone down the road...