What you want is called a chosen prefix collision. Given p1, p2 you want to find m1, m2 such that hash(p1 || m1) = hash(p2 || m2).
Generic attack
The generic attack to find this, is creating messages starting with p1 and just as many starting with p2. Thanks to the birthday problem you'll find a match after around 2n/2 messages.
For a 128 bit hash like MD5, this means you need about 264 operations. This is feasible in principle, but exceeds your budget. I guess it costs 200'000\$ if you use GPUs and 5'000\$ if you already have developed appropriate ASICs.
Exploiting MD5's weaknesses
MD5 is a broken hash function. Finding normal collisions is very cheap, but that doesn't help you. Luckily(for you) there is also a chosen prefix attack against MD5.
According to a paper from 2009 this costs around 251 compressions. Which corresponds to to about 18 GPU days on a GPU that cost 200\$ in 2009.
So I estimate that the attack costs 10-20\$.
There are two caveats:
The random characters are no printable ASCII characters, but rather random bytes.
It might be possible to modify the scheme to only emit printable ASCII, but I didn't investigate that.
There will be more random characters than your example has, probably somewhere between 70 and 130.