backing out of a module update after uploading it and before the database update (new update is incompatible with my version of PHP)
Should I delete the reCAPTCHA module from /sites/all/modules/, and then put the files for the old version in there?


Yes, that's exactly what you should do.


  If I do that, will the database updates script be confused?


They shouldn't be - when you start an update, the current versions of modules are queried from fresh again. So as long as the current version of the module in the database matches the version in the file system (which it will if you restore to before the file system change), you should be fine.