However, we are seeing:
The site is running 188.8.131.52 on MediaTemple. I just changed all MediaTemple passwords and C5 passwords.
When I clear the C5 cache, the bad links go away.
I'm assuming we've been hacked but I'm not sure how to clean up the site. Where would I look to see where/how these links are changing?
Perhaps you could check your files bi making an zip archive of your installation. Download this an check all files by date - especially the files with newer dates that you didn't touched. Perhaps you will find some unnormal files or inputs.
Check your index.php and htaccess in the root.
Can you compare it to a backup you have?
Perhaps you can replace the /concrete directory with an original download from the same version. Then at least this part should be save again.
I'm not an expert but these are some ideas for some actions.