One of the problems with Compaq is that they tend to use highly proprietary RAM modules in their system. An exception might be like Dell where you can throw in a wide variety of RAM (brands) and the system will still boot up fine.
You could risk going with a cheaper brand RAM (as long as it's compatible w/ your MB) but with a proprietary system like Compaq.... I wouldn't exactly count on it.
EDIT: Why do you say you can't go less than 256 MB? There is no such requirement that would limit you to that exact amount.