Sometimes I just ignore the impossible senate messages, particularly if all they are offering is another "exotic unit" rather than hard cash that will be dumped in my capital. I also tend to take a look and see whether I need to bother in case some other faction takes the city before I can get there. Somehow the senate always seems to come up with these dumb missions while I am finishing off some other faction at the other end of the world