It has been said that within the mountains (or was it the darklands?) there dwells a fluffy creature of immense cuteness. This creature is so adorable that all who encounter it are filled with joy so great their mortal forms cannot contain it. And they explode. Several magic institutions are desperate to study the creature or better yet capture one to prove the theory of an elemental plane of "D'Awwww".
The PCs are walking along the road, when suddenly a bunch of bandits attacks. The player's dismiss it has just a random encounter, when they find an ornate ring on the leader, obviously out of place with the seemingly poor bandits, who could only afford cheap leather and weapons. This ring has a symbol on it, which, if researched, sets the PCs on a quest. And from then on, the players don't look at random encounters the same way...