How to know if X and Y have coauthored?
In computer science, DBLP might be a better idea than MathSciNet. Your own page in DBLP lists all your coauthors; the database is certainly not complete, but usually the information is correct.

You can also try to use Google Scholar, with a search similar to this:

author:foo author:bar


As always with Google Scholar, double-check the results.