It appears to be more or less synonymous, and yes it appears often thoughout Tanach. The first instance of imadi is Genesis 3:12 (Adam blames G-d for "the wife you have put with me", imadi; the first time imi appears in Tanach is when Joseph's master's wife tells him "sleep with me" [imi].
A grammarian such as Malbim is likely to explain the nuanced distinction between imi and imadi, but I don't know what it is off-hand.
It appears to actually be the more-common form used both in Genesis and Job. Here are the counts I'm coming up with, based on parsing mechon-mamre's text, counting both "with me" and "from with me". (And yes, to do this properly you should eliminate cases of ami and amei instead of imi; but this is a first-degree approximation. Count the *imadi*s as the actual number, and the *imi*s as an upward bound; for instance, Lamentations is all ami's, no imi's).
I'm having trouble pasting code correctly into this template with the right right-to-left order thing working, so I'll do this all in English:
Bookname "imi" "me'imi" "imadi" "me'imadi"
Genesis 7 1 14 0
Exodus 17 0 2 0
Leviticus 4 0 1 0
Numbers 1 0 0 0
Deuteronomy 1 0 3 0
Joshua 2 0 0 0
Judges 5 0 1 0
Samuel 20 0 4 2
Kings 12 0 0 0
Isaiah 24 0 1 0
Jeremiah 30 0 2 0
Ezekiel 22 0 0 0
Hosea 10 0 0 0
Joel 4 0 0 0
Amos 5 0 0 0
Obadiah 1 0 0 0
Jonah 0 0 0 0
Micah 9 0 0 0
Nahum 0 0 0 0
Habakuk 0 0 0 0
Zephaniah 3 0 0 0
Hagai 0 0 0 0
Zachariah 2 0 0 0
Malachi 0 0 0 0
Chronicles 21 0 0 0
Psalms 11 0 2 0
Job 1 0 14 0
Proverbs 0 0 0 0
Ruth 4 0 0 0
SongOfSongs 1 0 0 0
Ecclesiastes 0 0 0 0
Lamentations 6 0 0 0
Esther 2 1 0 0
Daniel 9 0 3 0
EzraNehemiah 8 5 0 0
UPDATE: I've added v' forms as well. Here are the totals:
Bookname "imi/me'imi/v'imi" "imadi/me'imadi/v'imadi"
Genesis 8 14
Exodus 18 2
Leviticus 4 1
Numbers 1 1
Deuteronomy 1 3
Joshua 2 0
Judges 6 1
Samuel 20 6
Kings 12 0
Isaiah 24 1
Jeremiah 35 2
Ezekiel 22 0
Hosea 11 0
Joel 4 0
Amos 5 0
Obadiah 1 0
Jonah 0 0
Micah 9 0
Nahum 0 0
Habakuk 0 0
Zephaniah 3 0
Hagai 0 0
Zachariah 2 0
Malachi 0 0
Chronicles 22 0
Psalms 11 2
Job 1 14
Proverbs 0 0
Ruth 4 1
SongOfSongs 1 0
Ecclesiastes 0 0
Lamentations 6 0
Esther 5 0
Daniel 9 3
EzraNehemiah 14 0