@Danilo,
Sim, assim como o prerender, existem diversas outras soluções pra esse problema. Confesso que não sei se o crawler da google já está 100% compatível com SPA, mas a tendência é só melhorar.
No próprio artigo que você mandou tem um exemplo de implementação para manter a compatibilidade com o Google Analytics, o que adiciona mais complexidade à aplicação.
Assim como este problema com SEO, existem outros como por exemplo performance do primeiro acesso. Vários players importantes (como airbnb e netflix) já publicaram seus cases sobre como atacaram esses e outros problemas. Se você ler cuidadosamente, vai ver que seus processos passaram por decisões bastante complexas, como a mudança da stack (no caso do airbnb de rails pra node.js)
Minha intenção no e-mail anterior era só levantar o exemplo de um dos vários trade-offs existentes nessa abordagem que precisam ser levados em consideração na hora de tomar esta e outras decisões arquiteturais. Não se pode optar por esse caminho somente pelo fato de ser uma tendência (que a longo prazo acredito que vai se estabilizar) ou por que é "elegante".
Segue os links dos cases que citei acima:
Vale lembrar que os dois cases são de aplicações com demandas absolutamente incomuns e por isso também necessitam de soluções incomuns.
Abraços