Horrible frontend performance on large CCK forms = poor UX. What are my options?
I have exactly this problem and I can confirm answer #1 - using a multi-step form improved performance, although it was still slow.

The problem is that when the Ajax fires, the entire form is rebuilt in the background. This appears to make huge demands on the server CPU if the form is large.

A multi-step form is a good way of improving things but unfortunately will not always be appropriate - in my case, the client rejected it because they felt it was too annoying to have to progress through the form in a step-by-step linear way. They wanted to be able to jump from tab to tab without saving in between.

Other than fixing Drupal core so that rebuilding the form does not require 20 seconds of max CPU, the only solution I can think of is to try the site out on a high-CPU hosting package, e.g. on Amazon AWS. This will be my next step.

Without knowing much about Drupal core and Ajax, I would call this a bug of sorts. I have heard that the performance of Ajax is being improved in Drupal 8 so I seriously doubt much effort will go into resolving this in D7.

If I had known all this at the start of my project I might have tried solutions such as combining several node forms on one tabbed panel - to break up the server load in more creative ways.