I've tried to reproduce the problem you report but to no avail. You can clear GridView's SelectedItems collection in SelectionChanged event. I have prepared a sample project that you can find attached. Could you check it and let me know how it works on your side?
Check out Telerik Analytics, the service which allows developers to discover app usage patterns, analyze user data, log exceptions, solve problems and profile application performance at run time. Watch the videos
and start improving your app based on facts, not hunches.