Yes, sounds very well possible.
What is the frequency you want to update the car's position? I don't know the prioces of SMS's in your country but ...
Think you could send a new location depending on several factors:
- if location doesn't change - once per day is enough
- if location has changed more than 100 meters/yards from the last send location?
- in anti-theft modus make that 1 meter/yard
ANother option to consider is that the Arduino would send the location upon request. You send an SMS to the Arduino and it sends its current location back
Will cost you far less ...