Yet more proof that I over complicate things...

Found out that what I've been looking for (Sudoku with letters) actually has a name. It's Wordoku. Found a ton of Wordoku books @ Amazon.