iTunes purchase that you delete(these remain in iTunes cloud) show up in albums through BT audio. if you select one of these songs, it will download it through your phone(if the option is enabled on your iphone).

 

Do you have iTunes Match?

 

nope.

it's turned off, that's the thing, all of the itunes cloud/match settings are turned off on my iphone and itunes on my macbook, so it's weird how my car now completely throws that out the window and still displays deleted music.

 

Wow now that is weird lol. Guess the car has it's own taste in music.

 

Do you have "Automatic Downloads" for Music turned on or off?

Settings -> iTunes & App Store

 

Auto downloads will do it. Also you should have a cellular data option that you can turn off. There is also an option to hide these purchases when you are on iTunes using a desktop.