Upgrading to 1.5.1 or clean install? Need some tips

I had my store in ZC since 2009, and used just 1.3.8a, because of convenience, it was working and the upgrade was far too complicated ... but lately, really recently, I switched to a VPS and couple days since I was moved there my host shut it down because of scripts spiking and clogging the server!
This what they said >>

I believe the cause is poor coding and mysql queries that are taking far to long to execute. Somewhere there's a serious coding error or memory leak that makes your site perform poorly and it drains all of the system resources. A dedicated server would help, but more importantly if problems arise or you crash a server it only affects your sites while the server is rebooted.

After 8 days offline I decided to set the store in Web for maintenance and monitor the server, well the thing is i got spikes and my host is asking if even in maintenance mode the spiders can produce spikes as they did before

I was watching your site closely and it wasn't taking much traffic to bring the server to it's knees. The most recent crash was caused by a spidering of the site from Bing as it was going to the manufacturer pages. I believe it's a memory leak or something in the coding that's causing a loop. The processes start to backup until the server runs out of resources. I can try activating the site again if you'd like and keeping a close eye on it.

The pages are embedded with tons of links and the spiders are grabbing them all and then hitting 1 page per second:
157.55.33.253 - - [22/Jan/2013:04:11:10 -0500] "GET /electronics/index/manufacturers_id/386?page=1&sort=4a HTTP/1.1" 302 259 "-" "Mozilla/5.0 (compatible; bingbot/2.0; +http://www.bing.com/bingbot.htm)"
157.55.33.253 - - [22/Jan/2013:04:11:11 -0500] "GET /electronics/index/manufacturers_id/386?sort=1a&page=2 HTTP/1.1" 302 259 "-" "Mozilla/5.0 (compatible; bingbot/2.0; +http://www.bing.com/bingbot.htm)"
157.55.33.253 - - [22/Jan/2013:04:11:12 -0500] "GET /electronics/index/manufacturers_id/394?sort=2a&page=3 HTTP/1.1" 302 259 "-" "Mozilla/5.0 (compatible; bingbot/2.0; +http://www.bing.com/bingbot.htm)"
157.55.33.253 - - [22/Jan/2013:04:11:13 -0500] "GET /electronics/index/manufacturers_id/433?sort=20a&page=3 HTTP/1.1" 302 260 "-" "Mozilla/5.0 (compatible; bingbot/2.0; +http://www.bing.com/bingbot.htm)"
157.55.33.253 - - [22/Jan/2013:04:11:14 -0500] "GET /electronics/index/manufacturers_id/434?sort=20a&page=2 HTTP/1.1" 302 260 "-" "Mozilla/5.0 (compatible; bingbot/2.0; +http://www.bing.com/bingbot.htm)"

This type of activity then causes the server to fail since all of the processes simply backup in line behind each other.

--

So I'm trying to get rid of these problems, so in this case is it advisable to upgrade or is it better to start fresh?
I've seen the list of compatible add ons and I have so many that aren't listed, so I won't be able to upgrade those anyway ... my goal at this time is not to lose my VPS again, and have a functional store ... ASAP

Your symptoms sound like classic consequences of having been hacked because of old vulnerabilities in the old v1.3.8a version.

Step 1: http://www.zen-cart.com/wiki/index.php/Recovering_From_Hacks
Step 2: http://www.zen-cart.com/entry.php?3-How-do-I-rebuild-my-site-on-the-new-version-instead-of-upgrading

icecold:

I had my store in ZC since 2009, and used just 1.3.8a, because of convenience, it was working and the upgrade was far too complicatedSubstitute the words expensive, time consuming, etc for the word complicated, and you sound just like two of my clients who lost a few days (and one lost some dollars) because they didn't want to upgrade when I suggested, and ended up paying more because they had to do an emergency upgrade..

UPGRADE your site..