It is a dedicated server with Media Temple, the database is on the same box. It is a new store running 126.96.36.199.
The store has about 10,000 grocery items in lots of categories but, the store runs great, it is just the CRAZY 5 minute checkout time.
We are using Onestep Checkout and we have enabled it, and disabled it, set either way, checkout time was the same 5 minutes.
Our site is LIVE and the checkout time is killing me.