During the course of time i observed that, this multi-value parameter selection is being wiped of due to case sensitivity. I know that Sqlserver isnt case sensitive, but i dont know why.

The solution is while populating the parameter dataset better use "Upper(Ltrim(rtrim(City))) - value and Lable fields" in the dataset query and checked all of my datasets and it worked fine for me. Hope this isn't a permanent solution, but its working fine for me till date.

Don't forget to use to the same pattern in main dataset as some spaces may be trimmed.