Due to recent activity by the Klingon Empire, the lost Orion Fleet .. uh, I mean the Pirates near Orion have become very active. It is absolutely not to bring the Federation in to police the Klingons. But if the Federation happens to encounter Klingons outside of their borders while searching for Pirates, what-you-gonna-do?
So figure out a charismatic Pirate/Captain who is trying to draw the attention of the Federation without really doing too much damage, and have a rash of bizarre but attention-grabbing events to draw in the PC's and have them run into Klingons.
Board a civilian transport, and kidnap a diplomat or other VIP to ransom back (and secretly fall in love?).
Cripple the engines of a cargo ship, and threaten to destroy it if a ridiculous ransom isn't paid (but be ready to run off if a Federation ship appears - leading them perhaps to/near a secret Klingon outpost?)
At least, that is one idea.