Okay so I was able to modify the above code to suit my dequeue operation!
public T Dequeue()
{
var highestPriorityList = dictionary[dictionary.Keys.First()];
if (highestPriorityList.Count == 0)
{
dictionary.Remove(dictionary.Keys.First());
}
var topElement = highestPriorityList.First();
highestPriorityList.Remove(topElement);
return topElement;
}
Now I can dequeue for as long as I like without the InvalidOperationException which was caused by the missing element in the list after the RemoveAt operation!