Supongo que tu problema está en la tabla, ya que tener una tabla con todos los días de los años no es algo factible xD Se me ocurre hacer lo siguiente:
Por cada año, vas haciendo consultas de meses enteros con los días no-disponibles/parcialmente disponibles que estarán en la BD. Sobre si consultar a cada mes o por cada año entero, depende de la cantidad de ocupación, puedes generar un índice que contenga todos los días distintos ocupados, así puedes decir por ejemplo si es mayor de 400 generar cada mes una consulta. Esto sería, obviamente, con un bucle for.
Una vez tenemos nuestro resultado $row que contiene sólo los días ocupados/parcialmente ocupados, con la función date(); obtenemos el número de día (del 1 al 31) o de día y mes; por el otro lado tenemos un array inicado con null con índices del 1 al 31. Null significa día libre. Mientras recorremos $row, ponemos $array_resultado[$row] = 1. O lo que es lo mismo, el día ocupado deja de estar libre.
Una vez tengas este array sólo es necesario un foreach:
Código PHP:
foreach($array_resultado as $key=>$valor)
{
if(empty($valor))
<td class="libre">$key</td>
else
<td class="ocupado">$key</td>
}
Espero que se entienda bien la idea xD