I still haven't got this working, but I have found out some more. Maybe some of this will inspire someone else to come up with a solution.
I tried replacing the ComboBox with a TextBox, because the auto complete interface is the same, and I found that the behaviour is slightly different. With the TextBox it appears to work better, in that the Append part of the auto complete works properly, but the Suggest part doesn't - the suggestion box briefly flashes to life but then immediately disappears.
So I thought "Okay, I'll live without the Suggest functionality and just use Append instead", however when I set the AutoCompleteMode to Append, I get an access violation exception. The same thing happens with Suggest - the only mode that doesn't throw exceptions is SuggestAppend, even though the Suggest part doesn't then behave correctly.
I thought that it was supposed to be impossible to get access violation exceptions when using C# managed code, but anyway, the upshot is that I can't currently use a TextBox or a ComboBox with any kind of dynamic auto complete. Does anyone have any insights into how I could achieve this?