I could make the user install and use a Service-based database (SQL)

Well, this has the advantage that you don't need any support, because nobody would play your game.... please , dont force the user to install and configure some (not common) thirdparty software for just playing a game.

I could save all the valid words in XML files

This would be ok. As example, german has around 5 million words, lets say in average 10 letters, that would be ~50 mb of data, nothing you should worry about holding in memory. With some simple searching structure, you will have really good lookup performance (for a start even a simple binary search would do). So, keep it simple and stupid

Btw I also was wondering how people fill dictionaries like the one in Letter Quest. I mean, are they sitting there for months inserting every single word they know into a repository?

I'm sure , that there are data bases around to get whole directories. Maybe you need to pay for them, at least you need to convert them into your own data format.

Simplest thing:

1) a simple text file for the words (XML is way overkill), with a word on each line. Then,

2) in your code, read it line by line and put the words into a C# HashSet

Only if the performance of step 2 (which would need to run when your game starts) is for some reason too slow, then you can look at more complex options. Perhaps converting the text file offline to some binary format (say, a giant char array with a second array for the word indices) that you can load directly into memory. If the words are sorted you can use a binary search to look up a word. Or use a trie if you want to get real fancy: http://crpit.com/confpapers/CRPITV62Askitis.pdf

I don't understand... do you need more functionality than just looking up words to see if they exist? If not, why are you looking for a more complex solution?

Here's the C# code to read a text file of words into a HashSet. Lookup performance is constant time. It will be extremely fast.

            HashSet<string> wordList = new HashSet<string>();
            using (StreamReader wordlistFile = new StreamReader("wordlist.txt"))
            {
                string line;
                while ((line = wordlistFile.ReadLine()) != null)
                {
                    wordList.Add(line);
                }
            }

Here's a word list:

http://www-personal.umich.edu/~jlawler/wordlist.html

You absolutely don't need a database, nor do you need XML. Just Use a text file with one word per line, sorted in lexicographical order. Load each word into a hash set, or put them into a massive character array with words separated by a 0 (zero) character and do a binary search. Either option will be plenty fast.

If you want to get really fancy, you could likely optimize your search times using information like this.