How do I send Bitcoins back to the person that sent me them without asking that person for a address without querying a block explorer?
I already know that (given that the person has his own wallet and doesn't use a shared wallet service) I can look up the transaction with its txid on a block explorer and just use one of the source addresses, but can I do it without needing a block explorer, directly with bitcoind API calls?
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).
As the above poster mentioned, refunding to an input address can be unreliable due to shared wallets.
The merchant protocol (BIP 70) https://en.bitcoin.it/wiki/BIP_0070 offers a good solution to this long term, but it is still gaining adoption, and not widely used yet.
The solution we proposed to Overstock.com and other merchants at Coinbase was to send the refund to an email address (merchant's typically have these on file for the customer, who is signed in at checkout). This delivers their refund to a Coinbase account (via email), which is either their actual Coinbase account, or at an address where they can sign in to claim it. They can then move the funds anywhere they'd like.
While not perfect, this has been the best solution we've seen merchants adopt to date for refunds.
