Case closed. To make things fast, do the following:
Use the ip4r types available from http://pgfoundry.org/projects/ip4r, as pointed out by user bma. This type supports indexing where Postgres's (up to Postgres 9.3) native ones don't.
Do not use the ip4r type directly, but expand it into lower and upper values as suggested by user caskey and mentioned in the ip4r docs: https://github.com/petere/ip4r-cvs/blob/master/README.ip4r#L187
Given the above, if you're using type ip4 (assuming you're dealing with v4 addresses) for all compared addresses, then the planner will leverage indexes on those columns.
Thanks for the help, guys!