Esta foi a solução que eu precisava: link .
Em resumo, meu roteador estava recebendo um endereço IP que estava na lista negra de uso do SMTP. O ISP aparentemente mapeou o endereço MAC do roteador para esse endereço IP na lista negra, então configurei meu roteador para usar um endereço MAC pseudo-aleatório. Isso resultou no ISP dando ao meu roteador um novo endereço IP e, consequentemente, resolveu meu problema.
EDIT: Embora traceroute parece indicar que as coisas não estão funcionando como esperado. Aqui está a nova saída:
kylemart@nas:/$ sudo traceroute -n -T -p 587 smtp.gmail.com
traceroute to smtp.gmail.com (74.125.141.108), 30 hops max, 60 byte packets
1 192.168.143.1 0.448 ms 0.968 ms 0.999 ms
2 66.158.177.124 2.114 ms 2.032 ms 2.072 ms
3 208.111.0.123 2.090 ms 2.073 ms 2.057 ms
4 208.111.12.214 5.149 ms 5.181 ms 5.119 ms
5 65.158.121.12 13.068 ms 13.095 ms 13.077 ms
6 * * *
7 * * *
8 * * *
9 * * *
10 * * *
11 * * *
12 * * *
13 * * *
14 * * *
15 * * *
16 * * *
17 * * *
18 * * *
19 * * *
20 * * *
21 * * *
22 * * *
23 * * *
24 * * *
25 * * *
26 * * *
27 * * *
28 * * *
29 * * *
30 * * *
Nota: Os endereços IP foram manualmente (ligeiramente) ofuscados.