Spatial messaging is a direct extension to text and other multi-media messaging services that have become highly popular with the current pervasiveness of mobile communication. It offers benefits especially to mobile computing, providing localised and therefore potentially more appropriate delivery of nearly arbitrary content. Location is one of the most interesting attributes that can be added to messages in current applications, including gaming, social networking, or advertising services. However, location is also highly critical in terms of privacy. If a spatial messaging platform could collect the location traces of all its users, detailed profiling would be possible – and, considering commercial value of such profiles, likely. In this paper, we present emphAir-Writing, an approach to spatial messaging that fully preserves user privacy while offering global scalability, different client interface options, and flexibility in terms of application areas. We contribute both an architecture and a specific implementation of an attribute based messaging platform with special support for spatial messaging and rich clients for J2ME, Google Android, and Apple iPhone. The centralised client/server approach utilises groups for anonymous message retrieval and client caching and filtering as well as randomised queries for obscuring traces. An initial user study with 20 users shows that the overall concept is easily understandable and that it seems useful to end-users. An analysis of real-world and simulated location traces shows that user privacy can be ensured, but with a trade-off between privacy protection and consumed network resources.