There are definitely people who I don't see on recentlog because I've rated them 2, and I haven't cert'd them directly. But maybe you're right, and they just happen to be below 3 for me because someone I've cert'd has rated them low.
Update: no, it's instant ... I've just rated arthur and the entry below this one has disappeared. You are browsing at thresh!=0, right?
Upupdate: no, it's not instant! I experimented with rating mattl at 2, and I still see my previous rating next to his username, and still see him on the recentlog at thresh=3. Even if I certify mattl, I still see my old diary rating. Curioser and curioser.