Cuando un archivo está condificado en UTF8 con BOM, se agrega un caracter (
ver más info) que, lógicamente, es enviado al navegador.
Hay funciones de PHP que envían encabezados al navegador (session_start, header, set_cookie, etc.) y requieren que no se haya enviado una salida previa (BOM, espacio, salto de línea, html, etc.), es decir, ni siquiera un caracter.
En tu PC (localhost) funciona porque, seguramente, tienes activo un búffer de salida, que almacena contenido hasta completar determinada cantidad de caracteres y después lo envía al navegador; en 1&1 no tienes activo el búffer y por eso es que no funcionaban las sesiones.