Thanks for the various recent replies. I've managed to get a bit more diagnostic information which precedes the error messages I reported earlier. It was copied manually from the monitor from a recent boot crash, but I think it's accurate:
[<c0104b55>] ? do_IRQ+0x46/0x9a
[<c0103bb0>] ? common_interrupt+0x30/0x38
[<c019136b>] ? page_cache_get_speculative+0xc/0x30
[<c0191cad>] ? find_get_page+0x53/0x7a
[<c0192475>] ? filemap_fault+0x7b/0x343
[<c01a71c3>] ? __do_fault+0x41/0x2f6
[<c01a7765>] ? handle_mm_fault+0x2ed/0x664
[<c03a036d>] ? do_page_fault+0x2b2/0x2c8
[<c03a00bb>] ? do_page_fault+0x0/0x2c8
[<c039e7e3>] ? errorcode+0x73/0x78
I'm not by any stretch of the imagination a systems guru, so if anyone can see anything here which might indicate the source of the intermittent booting problem, I'd be grateful to hear from them.
This is part of a "backtrace", roughly the sequence of calls some process made at the time of the crash, it's meant to help the people who developed the code to recognize the exact process flow in case of crash.
Unfortunately it lack of the first part, that usually state the name of the module/process that crashed, but even if present, we are not the developers of the code, most probably some kernel module, so don't worry much about.

The most useful info we can obtain here is the name of the process/module that crashed, just to have an hint about what went wrong.
Also could be interesting to know if the crash happen always the same way ... i.e. always at time of start of plymouth, or at the time of the start of the Xserver ...
To clarify what's happening, the symptoms are that it is difficult to achieve the initial boot, but after success (usually involving a delay in selecting the GRUB menu option) the PC is perfectly stable (over several hours) and behaves completely normally.
Since starting this thread, I've become aware of discussion of a similar problem under the thread "Boot process still erratic" on the PCLinuxOS forum at
http://www.pclinuxos.com/forum/index.php?topic=94269.0 and tomorrow will try texstar's suggestions there to see where I get to, but don't let that stop anybody with good ideas from replying to this post!
Additionally there has been reports in the past about crashes (even intermittent like your), for some combination of hardware,
i.e. older video cards, older CPUs, older kernels.
Although you state your system is fully updated, but you don't mention the kernel, which doesn't update automatically.
What's your kernel ? (
uname -r from a terminal)
AS