I can confirm it.
Just tried to search my e-mails...It works fine when I search in "Current Folder", but it crashes when I select "Current Account" or "All Accounts"

I can confirm that bug too.
Link to downstream bug report: https://bugs.gentoo.org/show_bug.cgi?id=403281

*** Bug 670058 has been marked as a duplicate of this bug. ***

Thanks for the update. I cannot reproduce this too. I see why it crashed, but I do not know why that state happened. Actually, the gentoo bug gives a bit more details:
> (evolution:8180): evolution-mail-CRITICAL **: em_utils_connect_service_sync:
> assertion `CAMEL_IS_SERVICE (service)' failed
>
> (evolution:8180): camel-CRITICAL **: camel_vee_folder_new: assertion
> `CAMEL_IS_STORE (parent_store)' failed
> Segmentation fault

Which means that there happened something wrong with the 'service', which lead to this crash.

I believe it depends where you are staying when invoking the search. I tried to stay on one of local folders, under On This Computer, I also tried to stay directly on On This Computer, and I tried to stay in one folder of my IMAP account. None made evolution crash for me.

What I did is to change the scope to "Current Account", and then typing my search term for "Subject or Addresses contain" and then pressing Enter.

Is this reproducible while you are offline, or only when online? I tried both.

I think that the circumstances and details are crucial here, thus if you can provide some more information since evolution's start, what is the selected folder, from what account, what you presses/clicked on, and so on, then it may help to reproduce the issue.

I can reproduce this on my Debian sid box (and thus reported bug#670058 which has the same backtrace).

What I do is select the INBOX from my IMAP+ account, select  “Current Account” for the search bar, type anything in it, then validate with enter. Same thing happens if I select another folder in the account, or the account itself. It happens also when on a folder in “On This Computer”.

Hrm, works for me, even with IMAP+ account. Could you try to run evolution under valgrind and repeat the issue, please? You can do it like this:
   $ G_SLICE=always-malloc valgrind --num-callers=50 evolution &>log.txt

Make sure you've installed debug info packages for evolution-data-server and evolution of the same version as the binary packages (you probably have, thus just in case).

Created attachment 207688 [details]
valgrind log

$ G_SLICE=always-malloc valgrind --num-callers=50 evolution &>evolution_valgrind.txt

Some additional from GDB after evolution-data-server recompiling with debug info:

Starting program: /usr/bin/evolution 
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib64/libthread_db.so.1".
[New Thread 0x7fffe7040700 (LWP 22902)]
[New Thread 0x7fffe683f700 (LWP 22903)]
[New Thread 0x7fffd807d700 (LWP 22904)]
[New Thread 0x7fffd5e39700 (LWP 22905)]
[New Thread 0x7fffcffff700 (LWP 22906)]
[New Thread 0x7fffcf7fe700 (LWP 22907)]
[Thread 0x7fffcffff700 (LWP 22906) exited]
[Thread 0x7fffcf7fe700 (LWP 22907) exited]

(evolution:22899): evolution-mail-CRITICAL **: em_utils_connect_service_sync: assertion `CAMEL_IS_SERVICE (service)' failed

(evolution:22899): camel-CRITICAL **: camel_vee_folder_new: assertion `CAMEL_IS_STORE (parent_store)' failed

Program received signal SIGSEGV, Segmentation fault.
camel_vee_folder_set_expression (vf=0x0, 
    query=0x1253c00 " (or\n  \n       (match-all (header-contains \"Subject\"  \"a\"))\n     \n  (match-all (header-contains \"From\"  \"a\"))\n  \n       (match-all (or (header-contains \"To\"  \"a\")\n", ' ' <repeats 22 times>, "(header-contain"...) at camel-vee-folder.c:2187
2187	camel-vee-folder.c: No such file or directory.

Created attachment 207693 [details]
Camel debug info

CAMEL_DEBUG=all evolution >&camel_debug.txt

Created attachment 207702 [details]
valgrind log

Here's a valgrind log using the proposed command line.

Thanks for the logs. The valgrind log doesn't claim on a memory, which means that the state is somehow possible. This is the key:

> evolution-mail-CRITICAL **: em_utils_connect_service_sync:
> assertion `CAMEL_IS_SERVICE (service)' failed

gdb can stop on runtime warnings when you place breakpoint in g_logv, and I would like to see what is where when this first warning occurs. You can do that with a command like this:
   $ gdb evolution --ex "b g_logv" --ex r --ex bt

It might be easier if one of you could catch me on IRC, server irc.gimp.org, channel #evolution. I use to be there during Central European working hours.

Breakpoint 1, g_logv (log_domain=0x7fffddad28e6 "evolution-mail", 
    log_level=G_LOG_LEVEL_CRITICAL, 
    format=0x7fffeece9b32 "%s: assertion `%s' failed", args1=0x7fffffffc178)
    at /tmp/buildd/glib2.0-2.30.2/./glib/gmessages.c:456
456	in /tmp/buildd/glib2.0-2.30.2/./glib/gmessages.c
(gdb) bt

+ Trace 229680

Aha, nice:
	service = camel_session_get_service (
		CAMEL_SESSION (session), "vfolder");
	em_utils_connect_service_sync (service, NULL, NULL);

	search_folder = (CamelVeeFolder *) camel_vee_folder_new (
		CAMEL_STORE (service), _("Account Search"),
		CAMEL_STORE_VEE_FOLDER_AUTO);

These are relevant lines. Basically, the "vfolder" service was not found in running services, and the rest is just caused by it. I suppose you've disabled search folders, which I didn't think of before.

Indeed, sorry for not mentionnng it, it looks indeed relevant. Yeah, search folders are disabled here.

You are right, search folders was disabled. I couldn't find this setting in Evolution GUI, I found this setting in GConf. After checking key 'enable_vfolders' in '/apps/evolution/mail/display/', problem solved.

Created attachment 207844 [details] [review]
evo 3.2.x patch

for evolution;

Well, maybe not a patch in the usual meaning, because this enables search folders when user tries to search in current account or all accounts, which also means that the folder tree will contain the Search Folders, and the option will be enabled since now on. I didn't want to do this this way, but the other way I tried to do this caused bigger issues (other crashes).

The 3.3.5+ doesn't suffer of this, the underlying related bits changed there heavily due to other improvements, thus this is only for 3.2.x.

I'm committing this into gnome-3-2 branch, though it's rather dead branch, because there is not planned any 3.2.4 release for evolution, as far as I know.

Created commit b24bc34 in evo gnome-3-2 (3.2.4+, if at all)