According to the WA DMV website, emissions testing is only required by law in urban areas of Clark, King, Pierce, Snohomish and Spokane counties.

You may not have to worry about legality issues at all. Check local laws, but it appears to be pretty lax there

:edit: Oops, I guess youre in Snohomish... just check w/ your dmv and ask them what their laws regarding engine replacement are.