I'm not so sure. Here's a system that, during install time, has the language-pack-nl installed; but the cache is still wrong.

I'd still put my guesses on a difference in locale, update-gnome-menus-cache getting the locale wrong during install time.

And it gets weirder. We now install Acroread in the postinstall script and now:

Mar 25 11:22:36 in-target: Uitpakken van language-pack-nl (uit .../language-pack-nl_1%3a10.04+20100320_all.deb) ...
Mar 25 11:22:36 in-target: Overschrijven van de bestanden in het oude pakket language-pack-nl-base ...
Mar 25 11:22:37 in-target: Instellen van language-pack-nl (1:10.04+20100320) ...
Mar 25 11:22:37 in-target: Instellen van language-pack-nl-base (1:10.04+20100313) ...
(so here's language-pack installed)
[...]
Mar 25 11:32:38 in-target: Selecteren van voorheen niet geselecteerd pakket latex-xft-fonts.
Mar 25 11:32:38 in-target: Uitpakken van latex-xft-fonts (uit .../latex-xft-fonts_0.1-8_all.deb) ...
Mar 25 11:32:38 in-target: Selecteren van voorheen niet geselecteerd pakket libhx22.
Mar 25 11:32:38 in-target: Uitpakken van libhx22 (uit .../libhx22_3.2-1_amd64.deb) ...
Mar 25 11:32:38 in-target: Selecteren van voorheen niet geselecteerd pakket libpam-mount.
Mar 25 11:32:38 in-target: Uitpakken van libpam-mount (uit .../libpam-mount_1.32-2_amd64.deb) ...
Mar 25 11:32:39 in-target: Selecteren van voorheen niet geselecteerd pakket molly-guard.
Mar 25 11:32:39 in-target: Uitpakken van molly-guard (uit .../molly-guard_0.4.4-2_all.deb) ...
Mar 25 11:32:39 in-target: Processing triggers for man-db ...
Mar 25 11:32:41 in-target: Processing triggers for ureadahead ...
Mar 25 11:32:41 in-target: Processing triggers for hicolor-icon-theme ...
Mar 25 11:32:42 in-target: Processing triggers for desktop-file-utils ...
Mar 25 11:32:42 in-target: Processing triggers for python-gmenu ...
Mar 25 11:32:42 in-target: Rebuilding /usr/share/applications/desktop.nl_NL.utf8.cache...
(this is the last time desktop.nl_NL.utf8.cache is rebuilt; it contains wrong information here)

By the way, Perl keeps complaining:
Mar 25 11:34:30 log-output: perl: warning: Setting locale failed.
Mar 25 11:34:30 log-output: perl: warning: Please check that your locale settings:
Mar 25 11:34:30 log-output:     LANGUAGE = (unset),
Mar 25 11:34:30 log-output:     LC_ALL = (unset),
Mar 25 11:34:30 log-output:     LANG = "C.UTF-8"
Mar 25 11:34:30 log-output:     are supported and installed on your system.
Mar 25 11:34:30 log-output: perl: warning: Falling back to the standard locale ("C").
Mar 25 11:34:31 log-output: locale: Cannot set LC_CTYPE to default locale: No such file or directory
Mar 25 11:34:31 log-output: locale: Cannot set LC_MESSAGES to default locale: No such file or directory
Mar 25 11:34:31 log-output: locale: 
Mar 25 11:34:31 log-output: Cannot set LC_ALL to default locale
Mar 25 11:34:31 log-output: : No such file or directory

(And please note I'm *not* suggesting that Perl and Python are the same thing ;-)

Now we do the postinstall preseed-stuff and see:
Mar 25 11:34:36 log-output: locale: 
Mar 25 11:34:36 log-output: Cannot set LC_ALL to default locale
Mar 25 11:34:36 log-output: : No such file or directory
Mar 25 11:34:36 log-output: 
Mar 25 11:34:36 log-output: Rebuilding /usr/share/applications/desktop.C.utf8.cache...

Huh?