Um documento de vinte páginas pode ocupar quarenta megabytes ou duzentos kilobytes com o mesmo conteúdo visível. A diferença quase nunca está no texto.
Texto não pesa; imagem pesa
Uma página inteira de texto são alguns milhares de caracteres, e cada caractere ocupa pouquíssimo: o texto de um livro inteiro cabe com folga no espaço de uma única foto de celular. O que enche um PDF são as imagens incorporadas, e vale saber que uma captura de tela colada num documento é salva em resolução cheia mesmo quando aparece do tamanho de um selo.
Escaneado contra exportado
É a divisão que explica quase todos os casos. Um PDF exportado de um editor de texto contém texto de verdade: letras que o computador entende como letras. Um PDF escaneado não contém texto nenhum, e sim uma fotografia de cada página. Por isso um contrato de dez folhas escaneado pode pesar cinquenta vezes mais do que o mesmo contrato exportado, e por isso num dá para buscar uma palavra e no outro não.
Que margem a compressão tem
Depende de qual dos dois você tem. Num PDF exportado existe uma reescrita sem perdas que reorganiza o documento e corta o redundante sem tocar em um pixel nem quebrar o texto; costuma ganhar bastante e não cobra nada em troca. Num escaneado esse caminho rende pouco, porque o peso está nas imagens, e para descer de verdade é preciso recomprimi-las. Quando nem isso basta, a única saída é transformar as páginas em imagens de qualidade menor, perdendo o texto selecionável: uma troca que convém fazer sabendo.
O que fazer antes de comprimir
Se foi você quem gerou o PDF, olhe primeiro a origem. Reduzir as imagens antes de colocá-las no documento dá resultado melhor do que comprimir o PDF pronto, porque você evita guardar detalhe só para jogar fora depois. Se o documento já chega pronto, comprimir é a ferramenta que você tem, e vale começar com um objetivo folgado: cada megabyte tirado a mais se paga em qualidade.