As you and others have stated, the 4.2 upgrade will probably help. What does 'pfctl -vsi' say? Anything different?
If I were in your shoes, I'd do exactly what you are doing -- the 4.2 upgrade and search for NICs with better interrupt handling. In a previous life when I was doing a lot more pf than I am now, I used em(4) exclusively, but that was only because it was a good mix of performance and convenience. I seem to recall that, at least at one point in the past, some of the SysKonnect/Marvell cards were supposedly good with interrupt handling, but I cannot seem to find anything to back that up. What about the ever popular net.inet.ip.ifq tweaks? The following thread seems to touch on this issue (and others) a good amount: http://kerneltrap.org/mailarchive/openbsd-misc/2007/9/26/322759 Lastly, do you have any optimization set in your pf.conf? I've actually always used 'aggressive' and have found that it helps keep things tidy and rarely times out legitimate connections. Though I know being in edu makes things like this difficult. -jon