Bug 150910 added a new gnome_desktop_item_set_launch_time() API.  All users of
gnome_desktop_item_launch* should be using this API.  I will attach a patch in a
moment that does so.  Some comments on the patch, though:

1) It uses the slowly_and_stupidly_obtain_timestamp() function that really
shouldn't exist (see bug 144897).  However, the right thing to do is the same as
for bug 144897 so whenever that one is fixed correctly, this can be done at the
same time.

2) The main impetus for this fix was the original problem reported in bug
150910.  Unfortunately, I can't test because preferences:/// no longer appears
to be a valid location.  I don't know what other ways, if any, excersize this
code path.  If you can point any out to me, I'll test the patch, though it's so
simple that I can't imagine there'd be any problems with it.

3) Why does nautilus do part of it's own startup-notification (using the
startup-notification library directly), and use gnome_desktop for part of it? 
It just seems kind of odd...