In current version (Pg 9.0-9.3) there is no fast "fail-back" mechanism. You will have to follow official guidelines which state:
The former standby is now the primary, but the former primary is down and might stay down. To return to normal operation, a standby server must be recreated, either on the former primary system when it comes up, or on a third, possibly new, system.
So your second guess is correct: you need to go for complete rebuild of standby.
This arises from PostgreSQL internals, WAL format and timelines. Every time fail-over is done, it creates a new timeline. You can not safely use WAL files from new server (the one that was promoted) to replay on old server after it's revived.
From version 9.1 on, you have a tool for fast cloning of postgreSQL instances: pg_basebackup. You can also use filesystem snapshots (eg. LVM2 + XFS).
If you have a snapshot of primary postgres cluster from before the crash, and a series of WAL files from that time on, you can revive primary cluster from that snapshot and replay its WAL files. This is covered in the docs.
PS. Thanks for a good question - this is not so clear right out of the docs.