He encontrado una solución (al menos para los que tenemos ATI/AMD) para el problema de aparición de borde negro y caída de fps al jugar en pantalla completa.
En el portátil lo ponía a 720 y se ajustaba a 720 50Hz, por lo que los fps máximos eran 50 y aparecía marco.
En el sobremesa a 1080 y se ajustaba a 24Hz, también con marco y a 24 fps.
Lo que he hecho, siguiendo el consejo de un usuario de los foros de Steam, es lo siguiente:
1. Abrir el Catalyst Control Center -> Mis Paneles Planos Digitales -> Soporte de HDTV
2. Agregar una resolución, que será 4 pixels de alto menos que la que quieras jugar (para 1080 sería 1920x1076, para 720 sería 1280x716). Aplicar esa resolución.
3. Seleccionar esa resolución en el juego!
Al hacer esto no me bajan los Hz, se mantiene en 60, y solo pierdes 4 píxeles por arriba que es casi inapreciable.
Espero que os sirva!