Another idea. I tried lots of things before I got it to work. And I don't remember precisely what they all were. And some of those may have laid the groundwork, i.e. changed the state of something which eventually allowed the setxkbmap command to work reliably.

One of those things was piping through xkbcomp. The man page for setxkbmap (on Lenny) states:

USING WITH xkbcomp
If you have an Xserver and a client shell running on different comput-
ers and XKB configuration files on those machines are different you can
get problems specifying a keyboard map by model, layout, options names.
This is because setxkbcomp converts these names to names of XKB config-
uration files according to files that are on the client side computer,
then it sends the file names to the server where the xkbcomp has to
compose a complete keyboard map using files which the server has. Thus
if the sets of files differ significantly the names that the setxkbmap
generates can be unacceptable on the server side. You can solve this
problem by running the xkbcomp on the client side too. With the -print
option setxkbmap just prints the file names in an appropriate format to
its stdout and this output can be piped directly to the xkbcomp input.
For example, the command

setxkbmap us -print | xkbcomp - $DISPLAY

makes both steps run on the same (client) machine and loads a keyboard
map into the server.

I probably gave the full set of args to setxkbmap (except for device) and then specified the device to xkbcomp. The man page (on Lenny) for xkbcomp doesn't mention the -i device option but if you run xkbcomp -help you see that it accepts such.