What I would do is use a recent postgres version (9.3.4 and even 9.4devel (which is almost in feature-freeze anyway)), fix any database problems on those, and then (if your app really needs it) work back to fix it on legacy versions (i.e.: 9.2.8, 9.1.13, 9.0.17). It's time to drop support for 8.4 (I see you even still mention 8.3 on your pages...).
And RichardK is right: get yourself acqainted with EXPLAIN ANALYZE output (at least to the point where you can tell whether an index is used, and useful).
if you can't get it sorted out with an index, I still think partitioning is the best way to solve your problem. I think all the talk of stored proceduring is a red herring.
IRC freenode #postgresql is often full of people who relish this kind of problem, even if it is somewhat FAQ-ish (sometimes you have to be patient).
Do let us know how you solve this. I'm interested. (If it wasn't 8.4 I'd probably have setup a little trial example...)
update: changed order of paragraphs: first try appropriate indexing, if that fails, partition).