As a suggestion, check out http://www.surfme.com/ for hosting. Although I don't have an answer to as to why your host would shut down your site, unless they were already under stress from it's other users processes. Seems weird that one day your build would take less than 1 minute to build, and the next a healthy 10 minutes. Sounds like server overload to me, which I would suggest (if they let you put Links back up) that you run your builds in a cron job during off peak hours while CPU usage is at it's lower demand.

In relation to this type of problem, if large links DB files are what's causing heavy CPU usage, what would it take, in the way of adding extra code, to configure Links to utilize "Low Mem" so it doesn't use up as much CPU power?

A fairly power C program (Analog) takes advantage of Low Mem while reading in a 100MB log file in less than a minute during peak hours while it gather's it data, but it is possible for a cgi script to utilize the same to be a little more CPU friendlier?