Ao que parece, lambuja veio, via lambugem, de lamber. Quem havia de dizer?! Lambugem começou por significar ‘guloseima’, ganhando depois o sentido figurado de ‘ganho ou vantagem que se dá a alguém, especialmente para o aliciar’, que é o sentido com que lambuja é usado nos exemplos da pergunta.
Lamber (Aulete) vem já do latim lambere. Lambugem aparece em 1716 no Vocabulario Portuguez e Latino de Raphael Bluteau, com o significado aproximado de ‘guloseima, gulodice’ (grafia original e negrito meu em todas as citações):
Lambugem. Comeres de pouca substancia, com que antes se satisfaz a golodice, do que a fome.
Em 1789, o dicionário de Moraes Silva já acrescenta o sentido de ‘isco (para peixe)’ e de ‘ganho para aliciar’:
LAMBUGEM , s. f. Comeres gulosos. § A ceva [isco] a que os peixes acodem. § Sopas , que se recebem por favor. § Lucro tenuissimo, com que se engoda alguem.
O dicionário de Cândido de Figueiredo de 1913 acrescenta o sentido, que restringe ao Brasil, de ‘gratificação, luvas’.
Em 1964 o Dicionário da Sociedade de Língua Portuguesa já tem lambuja, que diz ser o mesmo que lambujem. Entretanto o dicionário Houaiss (Lisboa, 2002) diz que lambuja é brasileirismo e só tem alguns dos sentidos de lambujem. Passo a citar, desenvolvendo algumas abreviações:
lambujem s.f. (1552 cf. João de Barros, Décadas da Ásia) 1 ato de comer gulodices
2 guloseima, lambarice 3 resto de comida deixada nos pratos 4 Brasil mesmo que LAMBUJA
ʘ ETIMOLOGIA radical de lamber sob a forma lamb- + terminação -ugem […]
lambuja s.f. Brasil 1 lucro ou vantagem em jogo, aposta ou negócio 2 aquilo que se ganha ou dá além do estipulado; quebra 3 gorjeta, propina ʘ ETIMOLOGIA provavelmente alteração de lambujem […]
Algo parecido a esta evolução de lambugem, que de ‘gulodice’ passou a significar também ‘gorjeta, ganho que se dá a alguém’, aconteceu em Moçambique a refresco (Priberam 7), que adquiriu também o significado “recompensa, geralmente ilegal, a quem proporciona ou facilita um negócio lucrativo”.