TheIceman5's solution won't work because you can't have cookies that are set across multiple domains. This has nothing to do with session handlers, PHP or your own ones.
An solution might be to set 'X' number of cookies, one for each domain they could visit.
You could also just not use cookies, and pass the session ID through the URL instead. Probably the best solution.