Here is what I did it, please keep in mind that I am not by all means an optimizer guru, my site does not sale anything; it is used to deliver some info to my clients and potential clients, it is more of a content site with details on every phases of my job (web dev) I have no outbound links (Where should I link to? .. my competitors :) )
I performed a thorough reshaped, killed about 75% of the existing content, added new directories etc…
I kept on server the old files
Asked G to remove them from the serp
Did a permanent redirect via .htaccess
Resubmitted each new dir index

Took me about 45 days but I am back in business with G
And never have been in a better shape with MSN
FYI I do not spend a dime on web ad.