Pessoalmente, creio que em «espaço vazio» não estamos rigorosamente perante um pleonasmo, em que vazio repita, exactamente, o que significa espaço, na medida em que, se estiver ocupado, ou preenchido, continua a ser espaço. No entanto, em muitas situações, usa-se apenas o nome espaço para designar espaço vazio, em expressões como «Não posso entrar porque já não há espaço», ou «Não colei o meu desenho por não haver espaço».

Nos exemplos que apresenta, e tendo como base a minha sensibilidade de falante, creio que ambas as expressões — uso de «espaço vazio» ou, apenas, de «espaço» — estão correctas.