The Chinese/deli combo isn't all that rare, and many of the names are chosen to match. "Moishe Peking" and "Ginzberg & Wong" come to mind, though I don't know if either is still in business.

And there used to be (maybe still is)? a Scottsdale, Ariz., restaurant called "The Other Place." Great for those "let's not go there, let's go to..." discussions.