Hola otra vez:
Después de alguna prueba adicional he conseguido recoger el valor array que aparentemente contiene los valores seleccionados sin que salga el Warning maldito

.
Doy el hilo por terminado, ahora debo averiguar como grabar los valores en la BBDD. Dejo el código final por si le sirve a alguien:
Form (Gracias C2am

):
Código PHP:
<div id="BOXForm3">
<select multiple name="visibilidad[]" size="4">
<?php
//Creamos la sentencia SQL y la ejecutamos
$visibilidad="SELECT Visibilidad FROM privacidad";
$Visible=mysql_query($visibilidad);
//Mostramos los registros en forma de menú desplegable
while ($row=mysql_fetch_array($Visible))
{
echo '<option value="'.$row["Visibilidad"].'">';
echo $row["Visibilidad"];
echo '</option>';
}
mysql_free_result($Visible)
?>
</select>
<p>(Manten presionada la tecla CTRL para seleccionar más de una opción)</p>
</div>
La recogida de datos (Gracias Patriarka

):
Código PHP:
$Visible=$_POST['visibilidad[]'];
foreach($_POST['visibilidad'] as $key => $value){echo $value; }
Muchas gracias a todos, como decia terminator "golveré" o si lo preferís en Inglés "I'rr be bach"