In general a substance will vaporize if some fraction of its particles have enough energy (due to their temperature) to exceed their binding energy. Binding energy is the energy contained in the intermolecular bonds holding a substance together. It is definitely possible for the particles of a substance to have a binding energy that is substantially higher than thermal energy will readily provide.
No. While most liquids have fairly low binding energies (and thus, relatively high vapor pressures) there are liquids that will not evaporate in a vacuum, one example being ionic liquids. As I wrote above, the attraction between the ions of these liquids is strong enough that they do not evaporate over time.
If you know the Periodic Videos YouTube channel, they've had a couple of videos about these fluids over the past couple of years. (Here's a link to one, if you're interested.) One of them featured the behavior of liquids in a vacuum, but I can't seem to find the link; it may have been on a sister channel.
No, consider all of the asteroids, space ships, satellites, and such floating around in space. For all intents and purposes they will float around until the end of time without evaporating. Again, the reasoning is as I listed above. We also don't see the vast majority of solid objects here on Earth slowly evaporating away, which we would expect if sublimation were a concern in a vacuum. The reasoning is the same as above.
If the solid is very, very cold, it is less likely to experience sublimation since its particles' average energies would be very low. Even dry ice would not vaporize if its temperature were very close to 0 K.
Here is a phase diagram of both water and carbon dioxide that might help illustrate the situation. You can see that as the temperature of the substance decreases the vapor pressure of the substance also decreases. At a sufficiently low temperature the vapor pressure is effectively zero (below the x-axis of this chart.) There is always the possibility of a single atom or molecule gaining enough energy to vaporize or doing something weird like tunneling off of the surface of the substance, but the process is so slow as to be unmeasurable. Again, asteroids in the solar system have been hanging around for several billion years without subliming.
Picture from Wikipedia.
Note: Be careful if you look up phase diagrams of common substances. They often involve only a few points that are actually referenced and the rest is drawn with quite a bit of artistic license. Compare the phase diagrams of water here and here to see what I mean. They are often drawn without scales (or with minimal scales) and are sloppy at best.