60 years in France.

[caravel]

I know, I know! I just always need that next Arbalester, that next Halberdier, that next ship... XD Really hard to find time for agents! Except Bishops... Which I make in useless provinces and use to spy on enemy XD But Spies require Castles, and Castles can make Halbs/Arbs!

Bishops/alims actually make the best "spies", whereas spies and assassins make the worst spies, despite the nomenclature. Spies are actually best used within your own provinces and should only be sent on daring missions for short periods and then brought home. This is due to their tendancy to eventually get caught. Border forts are the real killer. Send a spy or assassin to a province with one of those and he's already dead. This is why the humble bishop or alim is best for snooping on your rival factions.

Emissaries are not so good for spying as the AI loves to hunt them down with assassins. You can use this to your advantage however and train emissaries to keep in your own provinces as bait, with your counterspies lying in wait. If you're ever playing as the English, Scotland is good for this if you build a port as the AI seems to like to send all sorts of agents through there.

Despite this, one of the best ways to valour up your spies is to send them to a rival faction's disloyal/recently captured province and trigger a revolt. It is a good idea to send them en masse, because even though the highest valour spy is the only one having effect, all of your other spies will gain valour as well if he succeeds in instigating a revolt. I tend to send in my highest valour spy with as many 0 valour spies as you like. When the revolt is triggered all of those spies become valour 1. Rinse and repeat (the real problem is when you're getting on nicely and suddenly the AI builds a border fort in that province, so if you had 10 spies there, it's not uncommon to watch the "your spy was caught" info parchment 10 times in a row).

Does spies' loyalty bonus stack?

No, this is how it used to work in STW. In MTW it was changed so that only the highest valour spy in the province affects provincial loyalty (happiness).

I.e if you have 5 spies in a region, does that give +100% loyalty?

The maximum loyalty visible in MTW is 200%, though it can be higher than this it only ever displays "200%". In STW it displayed the exact loyalty figure, so if the province had 320% loyalty, it would display it (better IMHO). The maximum effective loyalty is 120%. This guards against loyalist revolts and faction re-emergences. Anything below that and a faction that was thought to have been wiped out can reappear.

If that was the case it could actually help military move faster on conquest.

It still does, but you need to train the highest valour spies possible. IIRC that is valour 2 in the 1087 - 1453 campaign and valour 3 in the VI campaign. This is because the VI tavern/brothel tech tree reverts back to something closer to the STW original in VI. In the main MTW campaign it is difficult to get spies early.