ALL of your "problems" with order_id apparently not incrementing are related to a problem your server has with PayPal. It has *nothing* to do with your orders tables or auto_increment at all.

When you use the PayPal IPN / Website Payments Standard module to make payments, your server must wait for PayPal's server to contact your server to notify it of the payment. If *anything* goes wrong in that communication, you'll never see the order in your store.

See this article for troubleshooting steps to try to resolve the problems between your server and PayPal's server: http://www.zen-cart.com/wiki/index.php/PayPal

Also, switching to Express Checkout instead of Website Payments Standard/IPN will avoid the problems you mention.