Yo pondria un control data con la columna paises, y que al irse deslizando por los paises del data me muestre en un listbox las ciudades de ese pais. Si necesitas mas ayuda, te paso algun code

Nas.....bueno, supongo que cargar todos los registros en el comba y tal sabes. Yo lo que haría (y hacía  ) es hacerlo de alguna de las formas que digiste, por ejemplo la 1º no está mal:
PERU (PE)
ESPAÑA (ES)
ITALIA (IT)
Y cogería el ID_pais del seleccionado, por ejemplo de la siguiente forma:
y lo utilizaría en una consulta para encontrar las ciudades del pais. Sería crear un recordset y utilizar la consulta select * from tu_tabla where ID_pais=cod_pais. Inmediatamente le sumaría el resultado de esta consulta al otro combo (ciudades) y ya está resuelto. Sería algo así:
Esto es una idea general. Se puede hacer de multitud de formas. He supuesto que sabes crear recordset y demás (no se si enlazas a la bbdd por código, por control(ejem. adodc),etc). Si tienes alguna duda dilo y si pegas el código mejor . Ahhh, por cierto, todo esto se debe meter en los eventos que creas necesarios del combo1 (Ejemplo: combo1_click).
Respecto a la 2º pregunta, cargar el nuevo pais en el combo1 si modificas la tabla de los paises, se puede hacer de varias formas según la modifiques exteriormente a tu programa o desde tu programa. Si es desde tu programa te recomiendo que al mismo tiempo que modificas la tabla añadiendo (o eliminando) un pais, lo hagas también directamente en el combo....así ahorraras tiempo teniendo que realizar todo el proceso de nuevo de carga del combo. Y si lo haces externamente, pues tendrás que cargar otra vez los combos con los datos de la tabla.
En el combo2 de ciudades no hace falta introducir nada, ya que se actualiza siempre que le das en el combo1 a algún pais.
Espero que hayas cogido la idea y que te haya ayudado en algo. Ya sabes, si tienes alguna duda postea, que alguien te ayudará.
Saludos.

Bueno.....a mi tampoco me desagrada esa forma, pero vale, es cuestión de cada programador . Pues otra forma nada tediosa, y un poco pilla, sería coger las primeras 2 o 3 iniciales de los paises y compararlas con el campo ID_pais . Otra forma más profesional sería, como cada pais tiene solamente un ID único en la bbdd, pues con una consulta sql arrancada desde un recordset ("select * from tabla where pais=" & combo1.text, o con la funcion find del recordset...rst.find("pais=" & combo1.text). Esto te posiciona al registro que quieres, y puedes sacar la ID del pais encontrado. Sería Idbuscada=rst!ID_pais. Y ya teniendo el ID_pais, pues se lo pasas a la consulta del combo de las ciudades y solucionado. Espero que hayas cogido la idea.
Con respecto al segundo caso, ya te lo dije, si no quieres problemas, vuelve a cargar el combo desde la bbdd. Por cierto, no hay que cerrar y abrir el formulario para cargar los datos de la bbdd, no es necesario.
Saludos.