Pues siento deciros que Google si valora los enlaces .edu y .gov, ya que son enlaces con mucha autoriadad. Es decir, al igual que las paginas de PR alto, estos sitios suelen tener un PR alto de 7, 8 y sus subpaginas también tienen un PR alto. Y las páginas que las enlazan también tiene PR alto. Por lo que por eso se dice que son páginas con mucha autoridad.
Y Google amigos mio valora mucho que una página tenga mucha autoridad y la posiciona antes y más rapido que otras.
Por tanto, y llegamos a la conclusión, de que podemos decir que si enlazas con este tipo de páginas tu sitio subirá más rápidamente en los resultados orgánicos de Google. (A parte de que las pruebas que han hechos cientos de SEOs)
En cuanto a la dificultad de obtener enlaces, es por las instituciones que hay detras de ellos, por la construccion de la página en si o su política. Es decir, es raro que páginas de PR 8 dejen que dejes comentarios para hacer posicionamiento.
Ahora si conoces al webmaster de la página, o bien a alguna persona que tenga acceso a la misma dentro de la propia red de la universidad o de la institución, dejar enlaces seria bastante más facil.