Truth be known, your store has probably always been at hxxp://www.main.com/store - The webserver for store.maindomain.com was simply pointing to it.
As for adding the 'www' in front of 'store' the answer you were given is/was the correct one - The CNAME solution is to set the DNS as follows:
www.store.somedomain.com CNAME store.somedomain.com.
That way, any requests to "www.store.somedomain.com" simply ends up at 'store.somedomain.com'
I've no explanation as to why they would have dropped/altered the configuration to domain.com/store rather than leaving it as it was.
I noticed the another reply made comment "I don't know what search engines make of it, but I doubt it makes much difference" - Actually, it DOES make a difference. Many search engines put more 'weight' onto a URL like "store.domain.com" than they would "domain.com/store/". IE, using both stores were set up identical, the 'store.domain.com' will probably get a higher ranking in the search engines.
Cheers
Rod
Bookmarks