Comment by Ruthalas

While not ideal, I've found a usable solution.

This GitHub repo [1] has map files generated using OpenAddresses.

Load the appropriate one for your area and you can search using addresses in the normal format. They currently provide maps for North America, and are regenerated roughly monthly.

(Thank you pnoll1!)

[1] https://github.com/pnoll1/osmand_map_creation