The error is NOT in OsmAnd and NEITHER in OSM, but in the data used to create maps from OSM map data. This data is again from a third party being
geofabrik.de
That's why you don't see it in
openstreetmap.org and you do see it in OsmAnd.
polygons, or in short, polys are used to create maps from regions (continent, country, state, county, ....)
See attached screenshot out of JOSM from part of the Alabama poly of the region you are mentioning. The purple dashed line is the border. The dark-grey line with the yellow cross and square is a very small part of the poly used to generate the Alabama map. The outside of the poly is water. Therefore, the part of the country containing the road that should be inside the poly (but isn't), is also water.
OsmAnd is only using the polys that are available.
I just corrected the Alabama.poly and sent it to the
geofabrik.de guys so they can add it to their set (after verification). In 2-5 weeks the corrected map will automatically be available in OsmAnd.
If you can create OsmAnd map screenshots or give exact locations (high zoom level) of the other incorrect spots you saw, I can try to correct them as well.
Harry