Ok, try the followign (still assuming points are equally spaced in both row and column directions):
1. Use 0.5 KM distance to produce buffers.
2. If you have ArcGIS 10, run Minimum Bounding Geometry tool (Data Management toolbox - Features toolset) on the buffers, specify RECTANGLE_BY_AREA for geoemtry type and ALL for Group Option. You will get one rectangle around all the buffers.
3. Zoom out so that you see a lot of while area around your points. Run Create Thiessen Polygons tool (Analysis toolbox - Proximity toolset; requiring ArcInfo license) on the points; make sure to set Environment ... - Processing Extents to be "Same as Display". You should get square polygons around points, except at the edges where the polygons fill up the display.
4. Use Clip tool (Analysis toolbox - Extract toolset) to clip the Thiessen polygons by the rectangle from Step 2 above.
Is the result what you need?
If you want to automate the "Zoom out" part of Step 3, you can just set a large extent values, so that the Thiessen polygons go out of the rectangle.