He'd need to list all input transactions from blocks N... N+3 as a source of funds. This will allow the network to verify the transaction without having to do a search.

What I don't understand is how do they know which transaction is in which block. Do they build a mega map of all transaction-to-block relationships and look that up? This would grow like mad.

Seems as the number of transactions grows the cost of looking up the validity would become more than the cost to compute the hash. Maybe there would be separate parts of the network responsible for each task and they would split the transaction fees.