What you are describing is almost certainly the i386-on-amd64 problem.
Solution is to do one of the following (in my order of preference, your
criteria may be different than mine, of course!) :
* run OpenBSD/amd64 (where this problem doesn't exist)
* wait for 4.1 (where it is fixed)
* run -current (where it is fixed)
"fixed" is probably not quite the right word, several people suspect
the PAE support was PROVOKING a real problem elsewhere, but backing
out the PAE support seems to have either quit provoking it or pushed
it down to unseen levels. But then, it's an amd64, if you have no
reason to run i386 code on it, I'd recommend running amd64 on it...
Nick.