I use oggenc 1.0.1 with these switches
-q 1 -m 80

I want q 1 quality, but with no less then 80 kbps since the iRiver T10 does not play bitrates below that. The thing is some songs are encoded with bitrates going below 80. Is this a bug or am I using it wrong?

Any suggestions?

Try -b 80 -m (any value below 80(sugest:32)) and -M (any value above 80(sugest:112)),using the abr if it's the case.
EDIT 1: You are using Vbr, sometimes the quality desired will give you bitrates above the expected and sometimes below,to the encoder just matter the quality not the bitrate.

-b 80 -m 80 --managed

..Actually, since it will probably choke on 79kbps, try
-b 80 -m 82 --managed

oggenc 1.0.1 is quite old, check out aoTuV b4.51

note: --managed turns on the bitrate management engine, and drags encoding speed to a crawl, and doesn't do any favors in terms of quality

I noted that by reading the help page.
Right now I'm seeing very few songs being rejected by the player so I reencode them with q2 and everything works fine. Q1 seems to be 80kbps and q2 is 96.
I can't find aoTuV linux binaries, so I'm a bit stuck with the official package that came with my distro. I'm not worried yet. Besides the auTuV seems to be supporting q -2 and q -1, I can't go that low. q 1 in the minimum.

Or go fractional like -q 1.5

Did you even bother to look?

http://www.rarewares.org/quantumknot/oggenc-aotuv451.gz

aoTuV is more than just -q -2 and -q -1. It is the improvement in quality that counts, yes even in -q 1, -q 2, and so on.

Aoyumi did some mighty wonderful fine-tune of Ogg Vorbis encoding there

So if you're not using the latest aoTuV (now no longer beta, but Release 1), you're missing something real good.