David,
Site maps are great and there is no reason not to use one. Back in the day they were essential, now the bots are pretty good at following every URL. I have not used Attracta before, but plan to soon. I'll run some tests without it first, then with it to see if it changes anything.
I routinely test and re-test for SEO changing keywords and phrases. Sometimes it helps sometimes it doesn't, especially with Google.
I also use Bing webmaster tools...you'll get ranked there easily and in no time...as well as Yahoo. This will also help your rankings at Google, as the all index one another.
As far as that old stuff, it's most likely cached results within Google and it will disappear in time. Forwarding is not an issue.
I have seen your website many times...very nice job. We (our company) use A2 ... just a great hosting experience, fastest servers I've seen.
I'd like to ask just one question, why use the redirect? Why not just move your store from the store folder to the root folder?
I'm just sayin'.
Gordon