'With' originally meant 'against', as in 'withstand', and then replaced 'mid' (German 'mit'), which didn't survive Middle English.

Both wieder and wider are cognate with with. Mið lost out in English and wid in German. Prepositions and preverbs (or whatever you call the prep-like things that have attached themselves to verbs in IE lgs) are one of the hardest things to learn in a foreign language, mainly I believe because they are the left overish bits after nouns and verbs have been accounted for.