There's no such thing as recognizing a symbol that has never been encountered before. It will just be an abstract shape with no meaning - like what words look like to someone that doesn't know how to read.
Shapes become symbols over repeated exposure and with added meaning. We've seen heart or star shapes many times, and they usually mean 'like' or 'love', or 'good job' or 'star'. Shapes like this are universally recognized for many people but the exact meaning will be slightly different depend on the person and the context and it will be difficult to modify their meaning for most people. For example, no matter how hard you try, you will unlikely be able to make people think "poison" just by looking at a heart shape.
A shape that has never been encountered will need a label because it needs to be infused with a meaning. For instance, no one knew that the Nike symbol meant Nike without repeated exposure to both the symbol and the word. In this case the new shape referred to a new concept, so neither meant anything to anyone without repeated exposure.
A previously encountered shape that is getting an additional meaning added to it, like cloud shapes before cloud-computing, will be easily recognized but the new meaning might be forgotten unless it's reinforced over time. And if the new idea is too different from the more commonly held concept, it will probably be rejected.
To answer your question, an icon that has been in use before with a label will be more easily understood than an icon that has in use before with no label and a new shape with a new concept, and all three will be recognized over a shape that has never been used before at all and has no label to define it.