So called "block chain based refund" is not reliable with bitcoin.
The sending wallet may be a shared web wallet (blockchain.info, MtGox, e.g. any web site) and thus you cannot guarantee that any of change addresses in the transaction are controlled by the user. Even by exploring the block chain and knowing from which address the bitcoins arrived and where unspent change went, it is not guaranteed that if you make a refund to any of these addresses the sender receives the payment.
Instead, all refunds must be handled off-band and the refund bitcoin address must be asked separately.
E.g. SatoshiDice includes the following disclaimer (players basically must use a desktop wallet where the wallet software generates a change address and the wallet is not shared with other users):
IMPORTANT: Only use wallets that allow you to receive Bitcoin from the same address you sent from. If you're not sure, test by sending a bet for the minimum amount. If you get nothing back, then your wallet is not compatible. Note that some bets may require one confirmation before the win/loss value is sent back.
A just-dice.com FAQ regarding shared web wallet.
In the case you still want to pursuit change-address based refund you might find these links useful
Here is some more info (I have written this down some time ago, but I have not verified whether this is still valid):
Your bitcoind must run in a special: Since bitcoind/Bitcoin-qt 0.8, no transaction index is kept anymore by default, as it is not necessary for validation in the new database model. Instead, there is only a database of unspent transaction outputs, which has enough information to (slowly) locate transactions in block files. getrawtransaction uses this, but it only works for transactions that are not yet spent in the block chain. If you want to be able to look up historical transactions, you need to set the txindex=1 configuration option (or start with the -txindex command line flag). As this setting can only be set when the database is created, you'll need to rebuild it from scratch (using -reindex).