First of all, I'd say you need to revise your table structure:
Customers (CustID (pk, auto_increment), CustLastName, CustFirstName)
Orders (OrderID (pk, auto_increment), CustID, StatusID)
Statuses (StatusID (pk), StatusDescription)
History (CustID, Notes, Datestamp)
Referencing your customers by CustID rather than lastname/firstname will ensure that your database is more fully normalized. For more info, do a Google search on "database normalization".
Your customer enters their identifying info; if they don't exist, do an INSERT, then use mysql_insert_id right after the INSERT to get the auto_number you just created. Then you can INSERT into the Orders table using the CustID, and retrieve the OrderID using mysql_insert_id again, and so on. You get the picture.
As Chris noted, this is not really safe outside a transactional environment. Unfortunately, your web provider may not offer you any alternatives (InnoDB tables may not be available, for instance).