Interesting question. Basically, I'd say your hunch is right and your problem is more about word choice than about grammar. My impression is that we would most often say 'There was a strong wind,' but 'The wind was blowing hard.'
(We don't often use the simple past 'The wind blew' except in poetry, or with an adverb of direction to describe a specific single event: The wind blew us off our feet, blew the ship off course, etc. And you probably already know that 'hard' doesn't add -ly when it's used as an adverb; there's a word 'hardly,' but it means 'kaum.')
That said, it's certainly possible to use a form of 'strong,' but the question of which one is tricky. There is a word 'strongly,' but it's more often used in other contexts: e.g., to mean 'in a manner displaying bodily strength' (fight strongly, kick strongly while swimming), or just 'very much' (feel strongly about sth., protest strongly against sth., remind so. strongly of sth.).
'The wind was blowing strongly' also seems possible; in that case, you could say that 'strong' was just a more colloquial usage, like 'go slow'/'go slowly.' Or I think (though I'm still mulling this over) you might also be able to say something like 'The wind was blowing strong out of the south,' if you understand the verb as being almost like a linking verb. An analogous example might be 'The sun was shining strong on their faces.' With some of these words where a flat adverb alternates with an -ly form, one of the two forms does sound more idiomatic in certain contexts, but with this particular one it's hard to say. Or at least it is for me.
Sorry to be so indecisive, but this is the kind of thing that we native speakers don't usually stop to think about. Once you start analyzing it, it's hard to remember what you would have said most naturally, like when you stare at one word for so long that any spelling starts to look bizarre.
It would probably help to get a few other comments from native speakers. Maybe someone with a grammar book like Swan on hand would like to look this up.