Test your site here:
[
google.com...]
Just append your site/its domain to the end.
Answering your questions one by one (I'm not an expert at these sorts of things, but I'll try to help):
>> My first question is whether Google will de-index a site due to XSS?
Yep, I think they would. I'd imagine that Google would pick-up on this.
>> How long will the re-indexing take?
Once you are 100% sure that all the malicious code is removed, fill in a Google reconsideration request:
[
google.com...]
>> Would moving a site around 3 or 4 times possibly have the de-indexing affect?
I doubt it; people (especially those on shared hosts) can sometimes move hosts fairly frequently. Still, I'd try not to move anymore since (to partially answer your next question), I doubt that Google would blacklist an entire server.
>> How can I check whether the current server where it is hosted is possibly black-listed?
There's no easy way as far as I know. One thing you could try is to find your website's/server's IP address (ask your host if in doubt), then search Bing for:
ip:[server IP here]
And this will give you the sites hosted on your server too. If they are all really spammy and blacklisted, this might be a reason. Although to be honest I doubt it, since Google would (I imagine) know that good sites might move to a new host which might have some bad websites, etc.
>> Lastly is there a way to see if someone purposefully deleted our results from Google - is this kind of attack possible?
Nope, I wouldn't imagine it's possible. Assuming your robots.txt and all doesn't block the search engines, I'd imagine that it's the XSS code that is the cause here.
>> Register a new domain
I'd personally try the above first and foremost. I.e., ensure there's no XSS, check via the Google safe browsing tool, then submit a reconsideration request.
Starting again would take months (to start building SERP strength again) and it's hopefully not necessary. Do this as a last resort :)