What to do when paper is deemed in scope for the conference but not for the proceedings?
Should I formally submit the paper as-is. Would it be better to simply
  try to find a more appropriate place to publish? Or should I just
  consider it a lesson learned, forget about this paper, and move on to
  the next one.


In academia, you have to fight for papers you believe.  Reviewers can vary wildly in their assessments, and their assessments can be wrong.  Ultimately, if you feel that this is an appropriate place to publish, I think it's worth submitting it anyway and rolling the dice.  I have two caveats:


If possible, ask a third party in your field whom you respect about their opinion of the paper.
Think hard about why you think the paper belongs in the proceedings and, if possible, add a clear motivation to the text.



  Is there something I could have done up front to establish whether the
  paper was in scope or not? Perhaps in future it would be better to
  only submit to conferences where it's very clear that the paper is a
  good fit. This issue is likely to arise again for me, because my
  research is sort of at the boundary of two fields.


In general, you can write to people on the technical program committee of the conference (or the chair of that committee) with a brief explanation of your work and a request for an assessment of suitability.  It is important not to get discouraged from rejections ... they are common, sometimes for good reasons and other times for utterly stupid reasons.  The key is to learn what you can from the reviews, improve the paper, and resubmit where appropriate.