When is Treasure not Treasure? NPCs as Campaign Rewards

  For the last two game years the main party of my campaign has been building a joint stronghold - the soon-to-be-12th level Fighter is creating a large concentric castle which will contain a cathedral for the 9th level Cleric and two towers for the magic-users. The Thief will have a hidden fastness across the river, overlooking access to the castle. As usual I am using this as an excuse to vacuum wealth out of the characters' pouches, but it is also a huge use of treasure that isn't treasure.
  That's right; the characters are calling in favors, goodwill, and connections.
  The Dwarven architects and master masons? Working at 1/2 normal fee because the party did their king a favor game years ago. The troops protecting the place? Barbarians saved from a curse when the party was 4th level. The ship bringing in exotic materials? Doing it as a favor since the captain paid for the ship with treasures given by the characters. There are more examples, but you get the idea.
  But this only works if the DM is creating opportunities for players to build relationships between characters and NPCs. I started the (new, young) players out gently with a friendly publican named Boz. Garrulous and connected, Boz introduced the characters to their first 3 adventures - but he also introduced them to NPCs that didn't need rescuing or mercenaries, just people who lived in the city and frequented the same pub. Once they realized interacting with Boz was valuable in and of itself, they started doing the same with other NPCs.
  Soon they were friends with the officers of the merchant ship they had hired to carry them to a distant city. After fighting pirates together on a different trip (and having the 2nd officer save the life of a character) the crew of the Black Parrot became a fun part of the game with characters corresponding with the NPCs about matters like in-game family and trade. A mission to retrieve a rare component for a reclusive Diviner and her warrior husband led to the wizards of the party passing on information and even minor magics to her and, in return, receiving the occasional prescient letter from her. When she and her husband died it was much more than a plot point!
  When the party realized that they faced a foe too powerful for themselves they quickly sent dispatches to bishops and war chiefs, barbarian kings and crime lords, soon forging an impromptu alliance to save the world - all by utilizing their connections.
  So - how does a DM do this? Here are a few tips;
  1) Think about NPCs and flesh them out. I know, I know, this is about the most common advice to DMs ever. But it is repeated often for a reason. If the party is chartering a ship, name all of the officers and senior enlisted. Allow the party to interact with them. Same with Inns. And with caravans. Etc.
  2) Keep notes. I have 'the NPC box': a small filing box full of 3 x 5 cards arranged with alphabetical dividers. If the players have anything approaching meaningful interaction with an NPC I jot notes own during play. After the game that NPC gets a card in the NPC box that looks a bit like this;

  NPC Name            NPC Location
  Level/Profession/Alignment/Alliances
  NPC Stats, H.P. A.C.
  Gear, Magic items, etc.
  Characters Known
  When met, how met, where met
  important information the NPC knows (if any)
  Notes (may continue on back)

  Then I keep track of all future interactions on the card. Once every 2-3 months I go through the box and determine if any NPCs contact the characters. I also keep track of relationships between NPCs this way, especially if the NPCs were introduced by the characters!
  I keep a box for each of my campaigns.
  3) Have some NPC interactions pay off immediately. Did the party just rescue an Elven warrior from becoming the main course at a Hobgoblin convention? He might offer service to his rescuer (instant henchman) and, if that is refused, he might still stick around to help for an adventure or three. If sent off he might just send a bit of coin, or a weapon, or something to the party once he gets home. 
  4) Have some NPC interactions pay off much later. The 4th level party just saved King Snurri's lands from a horde of Goblin wolfriders? King Snurri pays them the agreed upon fee and rides off to rebuild the border forts and the characters sail back home, over the sea. That's it, right?
  Maybe. Or, maybe, King Snurri sends the now 9th level party an envoy to give them a book he found on a dead necromancer, a book with a few rare spells in it. he was too busy at the time to feast with them but he never forgot the party. Do this once or twice and at least some players won't forget NPCs, either, maybe sending off letters or gifts to NPCs to build that relationship.
  5) Don't be Galactica. What I mean by this is, while it can be fun and shocking to have a seemingly-innocuous or friendly NPC turn out to secretly be a bad guy, don't overdo it. Have I ever had a damsel in distress turn out to be a Shapechanged Greenhag? Yes. ONCE. Was the friendly linkboy in town secretly a wererat? Yes. ONCE. Keep the shocking twists to a minimum or the players will never trust any NPC.
  6) Don't count on it working out for the NPCs you think it will. I spent weeks lovingly crafting a Mage's Academy in the home city of the campaign. Fully developed members; names and stats for 12 servants; maps; unique magic items; rare spells; you name it. I had a score of plot hooks lined up and ready, even potential romances if the players wanted to go that route. I slowly introduced the NPCs and made their potential benefits obvious and...
  Zip. The players yawned rather collectively. The characters never met all the wizards let alone the multiple maids, butlers, and hostlers I had written up. Remember how I mentioned Boz the innkeep above? Yeah; he is a key NPC because I had to have someone give hooks to the players after they completely blew off all my hard work. I hadn't even named 'the guy who owns the Inn near the mage Academy' when the party decided that is where they were going to congregate.
  With a little hard work and some luck pretty soon your players will be part of a gaming world that includes a lot of 0-level NPCs that they really care about.