Suppose some recent hominins such as Neanderthal had a spoken language (currently, as far as I'm aware, we are uncertain if they did, but suppose we knew they did). If this were the case, would it be possible to uncover their influence on known language families through linguistics, or is the time gap so large that any influence would be essentially lost in the noise?
The proposal is complete science-fiction. Not only is it too far in time (and it is, by almost an order of magnitude, as the proto-language we know the most about was maybe spoken in 3500BC whereas the most studied recent Hominid group, Homo neanderthalensis, disappeared roughly 35,000 years ago) but the correct analogy would be to ask someone who is completely colorblind to find a slightly reddish ball in a mass of orange balls: the best we can do at present is trace (with great difficulty) the variation of Neanderthal's DNA in human populations. From this kind of data, it would already be extremely hard to get non-trivial results on the movements of populations leading to this distribution of Neanderthal DNA (especially as East Asian populations have the highest rate of Neanderthal DNA, quite counterintuitively, see for instance here). Of course, tracing the evolution of a delicate and transient cognitive and cultural phenomenon such as language is immensely harder than tracing population movements (for which we might at least hope to find archeological evidence). Not to mention the fact that questions on mutual influences between well-recognized family of languages (such as indo-european and uralic for instance) are already far beyond the scientific consensus on the historical evolution of languages.
To recap: even considerably easier problems both in the study of the influence of other hominid groups on Homo Sapiens and on past mutual influences in languages are currently totally out of reach. The project described is presently about as scientifically credible as reaching the speed of light with a steam engine.
I believe it is very much the case. Just listen to the way some people bark. (belated April first contribution)
... and more seriously, it is most likely that some animal cries (is that language) originated human words by imitation. They can first enter the language via onomatopoeias, and may later evolve on their own.
The best known example today is "tweet", but "bark" or "tchirp" could probably qualify too. Though the origin of "bark" could be different.
Regarding real language, such as may have been spoken by Neanderthal people, it is probably too far away in time, as was said.
Then there is the distinct possibility that intelligent communication requires structures that are universal, not because we are all similarly wired, but because that is what communication entails (which would then cause us to be similarly wired).
If a non-human specie evolved language independently of us, it could well be that their language structure would not surprise too much human linguists. Then, if such beings had influenced human languages 5 or 10 thousands years ago, possibly less, it might not even be detectable.