diff --git a/calendar/libedata-cal/e-cal-backend-intervaltree.c b/calendar/libedata-cal/e-cal-backend-intervaltree.c
index 0ed0dd9..f53f9c9 100644
--- a/calendar/libedata-cal/e-cal-backend-intervaltree.c
+++ b/calendar/libedata-cal/e-cal-backend-intervaltree.c
@@ -46,7 +46,7 @@ G_DEFINE_TYPE (EIntervalTree, e_intervaltree, G_TYPE_OBJECT)
 typedef struct _EIntervalNode EIntervalNode;
 
 static EIntervalNode*
-intervaltree_node_next (EIntervalTree *tree, EIntervalNode *x);
+intervaltree_node_next (EIntervalTree *tree, EIntervalNode *x, time_t start, time_t end);
 
 struct _EIntervalNode
 {
@@ -79,7 +79,7 @@ struct _EIntervalTreePrivate
 };
 
 static inline gint
-get_direction (EIntervalNode *x, time_t z_start, time_t z_end)
+get_direction (const EIntervalNode *x, time_t z_start, time_t z_end)
 {
 	if (x->start == z_start)
 		return x->end > z_end;
@@ -367,7 +367,7 @@ e_intervaltree_insert (EIntervalTree *tree, time_t start, time_t end, ECalCompon
 }
 
 static EIntervalNode*
-intervaltree_node_next (EIntervalTree *tree, EIntervalNode *x)
+intervaltree_node_next (EIntervalTree *tree, EIntervalNode *x, time_t start, time_t end)
 {
 	EIntervalTreePrivate *priv;
 	EIntervalNode *y, *nil, *root;
@@ -381,15 +381,25 @@ intervaltree_node_next (EIntervalTree *tree, EIntervalNode *x)
 	nil = priv->nil;
 	root = priv->root;
 
-	if (nil != (y = x->right))
+	/* If we have a (relevant) right-hand child, go right and then left
+	   as far as we can. */
+	if (nil != (y = x->right) &&
+	    compare_intervals (y->min, y->max, start, end) == 0)
 	{
 		/* find out minimum of right subtree of x (assignment to y is ok) */
-		while (y->left != nil)
+		while (y->left != nil &&
+		       compare_intervals (y->left->min, y->left->max, start, end) == 0)
 			y = y->left;
 
 		return y;
 	}
 
+	/* No (relevant) right-hand children. Everything down and left is
+	   smaller than us, so any 'next' node must be in the general
+	   direction of our parent. Go up the tree; any time the ancestor
+	   is a right-hand child of its parent, keep going up. First time
+	   it's a left-hand child of its parent, said parent is our 'next'
+	   node. */
 	y = x->parent;
 
 	while (x == y->right)
@@ -539,39 +549,27 @@ e_intervaltree_search (EIntervalTree *tree, time_t start, time_t end)
 	EIntervalTreePrivate *priv;
 	EIntervalNode *node;
 	GList *list = NULL;
-	GList *stack_start = NULL, *pos;
 
 	g_return_val_if_fail (tree != NULL, NULL);
 
 	priv = tree->priv;
 	g_static_rec_mutex_lock (&priv->mutex);
 
-	stack_start = pos = g_list_insert (stack_start, priv->root->left, -1);
+	/* Find first relevant node */
+	node = priv->root->left;
+	while (compare_intervals (node->left->min, node->left->max, start, end) == 0)
+		node = node->left;
 
-	while (pos != NULL)
-	{
-		node = (EIntervalNode*) pos->data;
-
-		if (node != priv->nil)
+	while (node != priv->nil) {
+		if (compare_intervals (node->start, node->end, start, end) == 0)
 		{
-			if (compare_intervals (node->start, node->end, start, end) == 0)
-			{
-				list = g_list_insert (list, node->comp, -1);
-				g_object_ref (node->comp);
-			}
-
-			if (compare_intervals (node->left->min, node->left->max, start, end) == 0)
-				pos = g_list_insert (pos, node->left, -1);
-
-			if (compare_intervals (node->right->min, node->right->max, start, end) == 0)
-				pos = g_list_insert (pos, node->right, -1);
+			list = g_list_insert (list, node->comp, -1);
+			g_object_ref (node->comp);
 		}
 
-		pos = pos->next;
+		node = intervaltree_node_next (tree, node, start, end);
 	}
 
-	g_list_free (stack_start);
-
 	g_static_rec_mutex_unlock (&priv->mutex);
 
 	return list;
@@ -677,7 +675,7 @@ e_intervaltree_remove (EIntervalTree *tree,
 		return FALSE;
 	}
 
-	y = ((z->left == nil) || (z->right == nil)) ? z : intervaltree_node_next (tree, z);
+	y = ((z->left == nil) || (z->right == nil)) ? z : intervaltree_node_next (tree, z, _TIME_MIN, _TIME_MAX);
 	x = (y->left == nil) ? y->right : y->left;
 	/* y is to be spliced out. x is it's only child */
 
diff --git a/calendar/libedata-cal/e-cal-backend-store.c b/calendar/libedata-cal/e-cal-backend-store.c
index 4818396..1b264be 100644
--- a/calendar/libedata-cal/e-cal-backend-store.c
+++ b/calendar/libedata-cal/e-cal-backend-store.c
@@ -410,7 +410,7 @@ GSList *
 e_cal_backend_store_get_components_occuring_in_range (ECalBackendStore *store, time_t start, time_t end)
 {
 	ECalBackendStorePrivate *priv;
-	GList *l;
+	GList *l, *lp;
 	GSList *list = NULL;
 	icalcomponent *icalcomp;
 
@@ -422,8 +422,10 @@ e_cal_backend_store_get_components_occuring_in_range (ECalBackendStore *store, t
 	if (!(l = e_intervaltree_search (priv->intervaltree, start, end)))
                 return NULL;
 
-	for (; l != NULL; l = g_list_next (l)) {
-		ECalComponent *comp = l->data;
+	/* Preserve the order by walking the list backwards, since we *prepend*
+	   each item to the GSList for efficiency reasons. */
+	for (lp = g_list_last (l); lp != NULL; lp = g_list_previous (lp)) {
+		ECalComponent *comp = lp->data;
 		icalcomp = e_cal_component_get_icalcomponent (comp);
 		if (icalcomp) {
 			icalcomponent_kind kind;
@@ -435,6 +437,7 @@ e_cal_backend_store_get_components_occuring_in_range (ECalBackendStore *store, t
 		}
 	}
 
+	g_list_free (l);
 	return list;
 }
 
