Por questões de integridade, i3-dmenu-desktop está procurando por todos os binários em $PATH e por .desktop arquivos em $XDG_DATA_HOME/applications [...]. O problema era que a variável $XDG_DATA_HOME não estava definida no meu ambiente.