Sí, tanto Medievo como Medioevo son formas válidas. Por ser el nombre de una edad o época histórica, lo apropiado es escribir estas palabras en mayúscula. Respecto al adjetivo, la forma predominante hoy día es medieval. En el resto de los derivados, el Diccionario panhispánico de dudas indica que las únicas formas normales prescinden de la o, como en medievalista o medievalismo.