For his "Pic O' The Day", Win Scott Eckert (major domo of the Wold Newton website) recently chose this comic book cover.
I imagine that within the borders of the Wold Newton Universe, such a team-up could be possible. The Batman of WNU would have been operating in the 1940s, and Sherlock Holmes would have been still active, thanks to his use of Royal Queen Bee jelly.
We might be able to employ the same reasoning in Toobworld as well. However, Holmes would have to still be going strong in the 1960's (and there are many Sherlockians who believe him to still be alive), because that's when the TV Batman was operating at his peak in Gotham City.
There were two TV movies about Sherlock Holmes emerging from cryogenic preservation in the 80's and 90's, so those wouldn't count. And they'd have to be delegated to an alternate Toobworld anyway, since Jeremy Brett is recognized as the official Sherlock Holmes for the TV Universe.
We would have to take it on faith that Holmes was able to survive into the 1960's. However, Holmes himself would say taking that on faith would not be logical without empirical evidence. (And Dr. Loveless would say that without doubt mixed in, faith is just flabby sentimentality....)