Your Dictionary approach is perfectly fine. I use in some places a Dictionary < object, ObservableCollection < string > >. This works well as long as you understand its limitations, such as that if you modify one of the collections (delete, insert, remove, etc...), you won't have the built-in notifications from the dictionary that you get with the observable collection itself. If you want a Dictionary that itself behaves as an 'observable' dictionary, you will have to create a custom class. I've done this and it works well with a few tweaks.
As far as performance is concerned, well it really depends on how you are using it. My custom dictionary is pretty much analog to the performance of a typical dictionary with an observable collection TValue.