That was a pretty clever move on their part, I'd say. A quick glance makes it sounds like "Every Widget ON Sale" - not just "for" sale. Plus, as you mentioned, it disambiguates their title from yours and that apparently helps them compete on Google.
It sounds like you need a business issue brainstorm, more than pure SEO advice. I assume your titles are dynamically generated, correct? That would be a kind of restriction on what you can do.
I think I'd print out the SERPs from a lot of queries and study them intensively for a while - see what ideas pop up. But as long as you're outranking that competitor, I would do anything too drastic.