What is the most complex kanji (in terms of number of strokes), whether or not it's actually used often?
That really depends what you mean by "kanji". Remember that kanji are derived from Chinese characters of which there are not a defined number.
The 常用 (general use) kanji set is the one prescribed for education in schools and treated as a "safe" list to use in newspapers and other publications. The 常用 kanji with the most strokes is currently 鬱 (as noted by atlantiza), with 29 strokes. However according to the usage stats given by KanjiDic2 it is not one of the 2500 most used kanji in newspapers, so while it's taught in school it would be likely be considered as a "tricky" kanji.
The 常用 kanji that does feature in the 2500 most-used by newspapers is 鑑, which KanjiDic2 places at the 1391st most commonly used kanji in newspapers, basically meaning all literate Japanese will know it.
Outside of general use it's a lot less difficult to define, as there are many classical kanji that very few people would know today, so the "one with the most strokes" really just depends on how much you want to search. For example, in KanjiDic2 it appears to be 䯂, with 34 strokes. This is not a widely-used kanji and much less likely to be recognised by the average person.
For common (常用) kanji, I think 鬱 has the most strokes - 29. It is probably not as common as 鑑, but it's not exactly rare either. It's used in 憂鬱【ゆううつ】 (depression, the way you feel after writing that kanji) and a lot of other emotion-filled words.
And for archaic ones, I've also heard that 䯂 has the most strokes - 34. It's so uncommon these days though that it's not even in my online dictionary.
The kanji of the koseki register, i.e. kanji that were registered as part of a name, are publicly accessible here.
Here is a list of the kanji by stroke count that are registered as part of someone's name. I can't say how often they are used, but at least they are not all just a figment of someone's imagination (or if they were, they at least managed to get them officially registered).
I list the stroke count (
X画) and separated them by kun'yomi (all kanji with 30 or more strokes) and on'yomi (all kanji with 40 or more strokes). There are many kanji with on'yomi only, and many of these were probably registered as part of a name from a naturalized foreigner with kanji name.